June 2019 update: altered the rounds from 96 to 192.  After living with 96 for a couple years, the delay was no longer noticeable, so I moved to a higher number of rounds.

If you’re feeling fancy, you can use the newer ED25519 format, you’d generate it with something along these lines:

ssh-keygen -a 192 -C ed25519-201609 -o -t ed25519 -f identity_file

That would leave you with an identity_file.pub to copy to your authorized_keys file on the remote servers.  One thing in the above to take note of is the -a 192 argument.  This is used to specify the number of key derivation function rounds to use to protect your private key from brute force attack; it is used when you specify the -o argument which stores the private key in ed25519 format; aka ‘new openssh format’.  The benefit here is that the ‘old’ way was using MD5 to protect your key, but with MD5 being easily processed by graphics card GPU’s, it’s, in theory, trivial to brute force or rainbow attack a stolen ssh private key file.  By applying a KDF to your private key and using a suitable number of rounds, you can make it much more difficult for someone to attack your file.  The default is I believe 16, which already goes from billions per second to perhaps a few attempts per second.  I decided to increase the number until I found the delay in authenticating my valid password to be just slightly less than annoying; 128 is where I ended up.  Going further and the delay is very noticeable.

Unfortunately, I’ve found some remote systems I want to SSH to do not work with ED25519 keys yet; certain network equipment for example, so after all was said and done, I ended up back on RSA keys.  That doesn’t mean you have to throw away the benefit of securing your key with ED25519 though; just use the -o and the -a args to get the same benefits there.  Here’s how to generate a 4096-bit RSA key stored with ED215519 and 192 rounds:

ssh-keygen -a 192 -b 4096 -C rsa4096-201609 -o -t rsa -f identity_file