As I understand it, crypto random generators do not have high-grade randomness as their primary priority. They have non-predictability, even if you know a large chunk of the previous number stream, as their primary priority.

The right thing to do is to replace Random with a different non-crypto generator with better properties. (Non-crypto generators don't care about predictability, only high-grade random distribution). Mersenne Twister seems the obvious choice, but it's about 1/2 the speed of java.util.Random. There are some other decent faster generators out there.