C# method for generating 4096 bit prime number slow

This is how I am using C# to generate a random 4096 bit prime number, the code just runs and runs and runs and I haven't yet had produce for me a result.

I would like to successfully create an implementation that is not dependant on existing code such as the C# RSA object or other libraries, but if that is the only way to create a function where I can provide the amount of bits and have it produce a random prime number then so be it.

I am looking for advice on how to improve this code to get the desired result.

public class RSA_RandomPrime
{
    // The random number provider.
    private RNGCryptoServiceProvider rng =
        new RNGCryptoServiceProvider();

    public BigInteger RandomPrime(int bits)
    {
        BigInteger rn =0;
        while (rn <= 0 || !PrimeExtensions.IsProbablyPrime(rn,256))
        {
            byte[] bytes = new byte[bits / 8];
            rng.GetBytes(bytes);
            rn = new BigInteger(bytes);
        }
        return rn;
    }
}

public static class PrimeExtensions
{
    // Random generator (thread safe)

    private static ThreadLocal<Random> s_Gen = new ThreadLocal<Random>(
      () => {
          return new Random();
      }
    );

    // Random generator (thread safe)
    private static Random Gen
    {
        get
        {
            return s_Gen.Value;
        }
    }

    public static Boolean IsProbablyPrime(this BigInteger value, int witnesses = 10)
    {
        if (value <= 1)
            return false;

        if (witnesses <= 0)
            witnesses = 10;

        BigInteger d = value - 1;
        int s = 0;

        while (d % 2 == 0)
        {
            d /= 2;
            s += 1;
        }

        Byte[] bytes = new Byte[value.ToByteArray().LongLength];
        BigInteger a;

        for (int i = 0; i < witnesses; i++)
        {
            do
            {
                Gen.NextBytes(bytes);

                a = new BigInteger(bytes);
            }
            while (a < 2 || a >= value - 2);

            BigInteger x = BigInteger.ModPow(a, d, value);
            if (x == 1 || x == value - 1)
                continue;

            for (int r = 1; r < s; r++)
            {
                x = BigInteger.ModPow(x, 2, value);

                if (x == 1)
                    return false;
                if (x == value - 1)
                    break;
            }

            if (x != value - 1)
                return false;
        }

        return true;
    }
}

I expect it to eventually report a random prime number to n bits but it appears to be stuck in a hopeless loop or I haven't give it enough time.