It's a thread contention problem as stated in the Java documentation

In other words, Since you are sharing an instance of Random to multiple threads, whenever one of the threads attempts to get the next Random number it has to "lock" the instance to perform the work and get the next number. At the same time another thread tries to generate a number with the same instance, it has to wait for the first thread to complete its work and release the "lock" before it can start for the next number.

Each instance of Random can only generate one number at a time.

With ThreadLocalRandom you eliminate that problem, because each thread uses it's own Random instance.