The RSA keys only need to generate two random primes of the appropriate size, so they can be generated fairly quickly. The DH moduli you generate will contain _many_ primes, and these are [safe primes](https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes#Cryptography) which take longer to find (prime _p_ is a safe prime if _(p – 1) / 2_ is also prime). Using safe primes for Diffie–Hellman moduli protects it from the [Pohlig–Hellman algorithm](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm). In addition, generating a single 4096-bit DH modulus requires finding a 4096-bit safe prime, whereas generating a single 4096-bit RSA modulus requires finding two _regular_ 2048-bit primes, which is much faster. This, combined with the fact that the modulus file contains many moduli, is why generating DH moduli takes so much longer. For both the RSA key and the DH moduli, you want to select 4096 bits. The `-a` option determines the number of KDF rounds used for decrypting your private key on your client with a passphrase. You want to make this as large as possible while not taking so long that it is annoying, assuming you wish to password-protect your private key. What this does is slow down a potential brute force attack against your private key. This flag _also_ increases the number of primality tests done on generated keys to the number you specify, if you are generating DH moduli. Anything above around 64 will be plenty. Letting it use the default (100) is just fine and there's no real reason to increase it. The second half of my answer explains why this is in further detail. Remember, a large RSA key makes it more difficult for an attacker to falsify authentication, and a large DH modulus makes it difficult to decrypt your session key and read (or modify) encrypted traffic. Using a custom modulus instead of an existing, common one protects against [logjam](https://security.stackexchange.com/q/89689/106285), although not as much as simply choosing a larger modulus (e.g. a custom 1024-bit modulus does not provide as much security against precomputation attacks as using a public 2048-bit modulus). --- You also asked in your bounty: > I would like to see algorithmic issues e.g. in the prime tests running on a standard PC considered. Most prime generation uses the [Miller–Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test), which I explain in more detail [in another answer](https://security.stackexchange.com/a/176396/106285). This is a probabilistic test which can determine that a prime is composite with 100% certainty. It can only determine that a number is prime with at worst 75% certainty. That is, the test will return either "certainly composite" or "probably prime". Prime numbers will _always_ return "probably prime", no matter how many times the test is run. Composite numbers will only return "probably prime" at most 1/4th of the time. If the test is run multiple times in a row, the chance that a composite number consistently fools the test into thinking that it's prime is astronomically low. OpenSSH uses 100 rounds by default, so the chance that a generated prime is not actually prime is, at worst, 4<sup>-100</sup>. There are deterministic algorithms such as the [AKS primality test](https://en.wikipedia.org/wiki/AKS_primality_test) that can determine with 100% certainty whether or not a number is prime, but they are _significantly_ slower and do not provide a meaningful increase in security, so probabilistic tests are used instead. The chance of accidentally generating a composite instead of a prime after 100 rounds is, at worst, the chance of guessing a 200-bit key _on your very first attempt_! Knowing that, you can see why a PC can generate prime numbers with more than reasonable certainty that they are indeed prime. Using `-a` to adjust the number of primality tests has much less of an impact on the amount of time it takes to generate primes than using `-b` to adjust the size of the primes. The reason for this is that it specifies the _maximum_ number of primality tests to perform before concluding that the number is indeed prime. The vast majority of numbers are composite, so the vast majority of candidate primes will be discarded after only a few rounds because there's no reason to keep testing a number that has been confirmed to be composite. It doesn't matter all that much if you specify 100 or 1000, because only the numbers that actually _are_ prime will go through (and pass) every test. The first time the Miller–Rabin algorithm returns "certainly composite" for a number, there's no reason to keep testing it and OpenSSH can go on to the next candidate. --- Another thing to be aware of, which dave_thompson_085 pointed out in a comment, is that modern OpenSSH implementations support better algorithms like Ed25519 for authentication and Curve25519 for key exchange. Curve25519 does not require generating prime moduli to work and Ed25519 keys can be generated far more quickly than RSA keys because it is unnecessary to generate random primes. Both these algorithms are extremely secure and should be preferred when possible.