Threshold Paillier encryption key generation time

I have used the threshold version of Paillier encryption without a trusted dealer in an application. I have tested the key generation phase with different security key sizes such as 80, 512, 1024, and 2048 bits.

With each security size, the key generation time is different and unpredictable due to the randomness involved in it. Let's say, with 80 bits, sometimes it takes 20 seconds and sometimes 20 minutes.

Is there a way to deal with this randomness? Any way to reduce the key generation time?

Assuming a party can be trusted for key generation (which may or may not be the case in the question), key generation time in Paillier encryption is about that for RSA with $N$ of comparable size.

To generate a key with $k$-bit public modulus $N$, and say $k\ge2048$, it's enough to independently generate two primes $p$ and $q$ essentially random in $(2^{(k-1)/2},2^{k-1})$ just as one would do for RSA. The public key can be $N=p\,q$ with $g=N+1$ implicit, and the private key can be $(N,\lambda,\mu)$‡ with $\lambda=(p-1)(q-1)$ or $\lambda=\operatorname{lcm}(p-1,q-1)$, and $\mu=\lambda^{-1}\bmod N$.

Is there a way to deal with this randomness?

Not entirely. That's an issue with RSA, thus Paillier: key generation time tends to vary (or be impractically long) because we sometime need to restart and try another candidate, and there's no practical upper bound to how many candidates we may need to test.

Any way to reduce the key generation time?

Yes. The techniques are the same as for fast generation of RSA primes. A common reference is FIPS 186-5 appendix A.

Perhaps the most common technique uses either sieving or other constructive generation of pseudorandom candidates known coprime to small primes, then a fast pseudoprime test (the strong pseudoprime test to base 2 is a favorite), then some other test(s) like more pseudoprime tests to random bases in $[3,p/2)$, and/or some different test (e.g. the Lucas test in FIPS 186-5 appendix B.3.3, or Damgard&Frandsen's An Extended Quadratic Frobenius Primality Test with Average- and Worst-Case Error Estimate).

Another avenue is Maurer's Fast generation of prime numbers and secure public-key cryptographic parameters.

With an optimized implementation, we are talking a fraction of a second in the vast majority of cases on a modern PC for 4096-bit (or smaller) $N$.

I have no experience with distributed generation without trusted party. Perhaps see Hazay, Mikkelsen, Rabin, Toft, and Nicolosi's Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting (originally in proceedings of CT-RSA-2012).

‡ It may be good to have $p$ and $q$ in the private key, for that allows a speedup by a factor approaching four, see this answer.