Fastest, thread safe way to create crypto-random n

Noticed that the crypto-random number generator isn't thread safe when generating random numbers in parallel over multiple threads. The generator used is RNGCryptoServiceProvider and it appears to repeat long stretches of random bits (128 bits). The code to reproduce this is shown below.

Short of using a lock to guard access to the RNGCryptoServiceProvider instance (which kills the whole speed point here), does anyone have a faster way to generator crypto-random numbers?

using System;
using System.Runtime.Caching;
using System.Security.Cryptography;
using System.Threading.Tasks;

namespace ParallelRandomness
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new Test();
            Console.Write("Serialized verion running ...  ");
            test.Run(false);
            Console.WriteLine();
            Console.Write("Parallelized verion running ...  ");
            test.Run(true);
            Console.WriteLine(Environment.NewLine + "Done.");
            Console.ReadLine();
        }
    }

    class Test
    {
        private readonly RNGCryptoServiceProvider _rng = new RNGCryptoServiceProvider();
        private readonly byte[] _randomBytes = new byte[128 / 8];
        private int collisionCount = 0;
        private readonly object collisionCountLock  = new object();

        public void Run(bool parallel)
        {
            const int numOfRuns = 100000;
            const int startInclusive = 1;
            const int endExclusive = numOfRuns + startInclusive;
            if (parallel)
                Parallel.For(startInclusive, endExclusive, x => GenRandomByteArrays(x));
            else
            {
                for (var i = startInclusive; i < endExclusive; i++)
                    GenRandomByteArrays(i);
            }
        }

        private void GenRandomByteArrays(long instance)
        {
            _rng.GetBytes(_randomBytes);
            var randomString = Convert.ToBase64String(_randomBytes);
            var cache = MemoryCache.Default;
            if (cache.Contains(randomString))
            {
                // uh-oh!
                lock (collisionCountLock)
                {
                    Console.WriteLine(Environment.NewLine + "Instance {0}: Collision count={1}. key={2} already in cache. ", instance, ++collisionCount, randomString);
                }
            }
            else
            {
                MemoryCache.Default.Add(randomString, true, DateTimeOffset.UtcNow.AddMinutes(5));
                Console.Write(instance % 2 == 0 ? "\b-" : "\b|"); // poor man's activity indicator
            }
        }
    }
}

The documentation for RNGCryptoServiceProvider states:

This type is thread safe.

Your code doesn't demonstrate that RNGCryptoServiceProvider is not thread-safe, since you use the same array in multiple threads. That array reuse is not thread-safe even if RNGCryptoServiceProvider is.

Regarding performance I want to note that creating a new instance of RNGCryptoServiceProvider is very cheap. The expensive part is the per-call overhead of GetBytes.

So if you have performance trouble, the first thing I'd try is asking for more data in one go and splitting it yourself. If that's still not enough, use a stream cipher seeded by the system CSPRNG.