シード値をとらないコンストラクタを使う，という選択肢はだめですか？
複数の乱数系列が欲しい場合を除くと，悪くない解だと思いますが。

System::Random* r = new System::Random();
int j = r->Next(0,10);

> うまくいきません。
どう上手くいかないのでしょうか？

System::Random* r = new System::Random( ( int )System::DateTime::Now.Ticks );

では上手くいかない？

YuOさんもおっしゃっていますが
> 複数の乱数系列が欲しい場合を除く
のならば、引数なしで十分ですね。

以下MSDNより
> Random コンストラクタ ()
> 時間に応じて決定される既定のシード値を使用し、
> Random クラスの新しいインスタンスを初期化します。

> Random コンストラクタ (Int32)
> 指定したシード値を使用して Random クラスの新しいインスタンスを初期化します。

> DateTime.Now プロパティ
> このコンピュータの現在のローカルな日付と時刻である DateTime を取得します。

> DateTime.Ticks プロパティ
> このインスタンスの日付と時刻を表すタイマ刻み数を取得します。

答えは出てるようなので、俺はうんちく担当。

> シードの値と言うものが良く分からないんですが、教えていただけませんか？

シードってのは「種」という意味。
乱数を生成する元になる値という意味です。

そもそも、コンピュータで生成する乱数は完全な乱数ではなく、擬似乱数といいます。
本当は出てくる値に規則性があって、完全にランダムではないんだけれど、その規則性
を簡単には予測できないような値を生成します。

で、
1.最初に適当な値を与える（これがシード値）
2.シード値をもとに計算し、最初の乱数を生成する
3.先ほど計算した値をシード値として計算し、次の乱数を生成する
4.以降繰り返し
という仕組みになっています。
この繰り返しのことを「乱数系列」と言います。

みなさんありがとうございます。
詳しい説明とてもありがたいです。

何がまずくてうまくいかなかったのか？
アドバイスを受けてどのようにしたのか？

をちゃんと明記しましょう。