ループの度にRandomクラスのインスタンスを作ってるんじゃないの?
インスタンスを作った直後のシード初期値って毎回同じじゃなかったっけ?

ループ内でインスタンスを作った後に時刻を元にシード更新するか、
ループ前でインスタンスを作って、ループ内ではRandom#nextIntするか
のどっちかにすればいいと思う。

最近、程度の低い問題で 推論→トライアンドエラーで解決 が出来ない奴多すぎ。
もうちっと頭使えよ。