Most users would simply type ssh-keygen and accept what they're given by default.
But what are the best practices for generating ssh keys with ssh-keygen?
For example:

Use -o for the OpenSSH key format rather than the older PEM format (OpenSSH 6.5 introduced this feature years ago on 2014-01-30)

How should one calculate how many rounds of KDF to use with -a?

Should -T be used to test the candidate primes for safety? What -a value to use with this?

For the different key types, what are the recommended minimum -b bit sizes?

etc... (there are a mind-boggling set of options in the manual page).



I recommend the Secure Secure Shell article, which suggests:
ssh-keygen -t ed25519 -a 100

Ed25519 is an EdDSA scheme with very small (fixed size) keys, introduced in OpenSSH 6.5 (2014-01-30) and made default ("first-preference") in OpenSSH 8.5 (2021-03-03).  These have complexity akin to RSA at 4096 bits thanks to elliptic curve cryptography (ECC). The -a 100 option specifies 100 rounds of key derivations, making your key's password harder to brute-force.
However, Ed25519 is a rather new key algorithm (Curve25519's popularity spiked only when it was surmised that other standards had been diluted) and its adoption is not yet universal. Large steps were made in 2018, so we're nearly there, but on older systems or for older servers (like CentOS/RHEL < 7 or Ubuntu < 15.04), you can generate a similarly-complex RSA key with 4096 bits:
ssh-keygen -t rsa -b 4096 -o -a 100

(You may need to omit the -o option since it requires OpenSSH 6.5+ and is the default starting in v7.8, at which point it was removed from the ssh-keygen man page. This dictates usage of a new OpenSSH format to store the key rather than the previous default, PEM. Ed25519 requires this new format, so we do not need to explicitly state it given -t ed25519. A previous man page stated that “the new format has increased resistance to brute-force password cracking.” See this answer for more detail.)
Do not consider the other new ECC algorithm called ECDSA.  It is considered suspect (it has known weaknesses and since the US government has been involved in its development, it may be compromised beyond that). Ed25519 was developed without any known government involvement.
Stay well away from DSA (“ssh-dss”) keys: they're not just suspect, DSA is insecure.
