I've been meaning to add this as a post, as it's light and quick, but as the release of OpenSSH 5.7, Elliptic Curve Cryptography has been implemented. Why should you care? The generated keys are substantially smaller, the algorithm is faster and lighter, giving a break to slower CPUs and the cryptanalysis hasn't shown any substantial weaknesses, unlike traditional RSA or DSA.
To generate an ECC SSH key for your host, you need to use the "ecdsa" encryption type. The bit strengths are 256, 384 and 521. Generally speaking, the equivalent DSA keys would require 4-times the bit strength of ECDSA keys. In other words, a 256-bit ECDSA key is equivalent in strength to a 1024-bit DSA key.
Pull up your terminal, and type:
% ssh-keygen -t ecdsa -b 256
Go through the prompts, and you should have your generated private and public keys. Then, copy the key over to your remote server, and start using:
% ssh-copy-id -i ~/.ssh/id_ecdsa.pub firstname.lastname@example.org
Of course, the remote server does need to support ECC in order to take advantage of ECDSA keys, which means it too needs to be running OpenSSH 5.7 or later. Here's a result of the key sizes:
% ls -l ~/.ssh/*.pub -rw-r--r-- 1 aaron aaron 604 Feb 17 20:05 id_dsa.1024.pub -rw-r--r-- 1 aaron aaron 176 Feb 17 19:41 id_ecdsa.256.pub -rw-r--r-- 1 aaron aaron 220 Feb 17 19:42 id_ecdsa.384.pub -rw-r--r-- 1 aaron aaron 268 Feb 17 19:42 id_ecdsa.521.pub -rw-r--r-- 1 aaron aaron 228 Feb 17 20:07 id_rsa.1024.pub -rw-r--r-- 1 aaron aaron 398 Feb 17 20:08 id_rsa.2048.pub
As you can clearly see, ECDSA keys are substantially smaller compared to their DSA counterparts and a bit smaller than equivalent RSA keys. Also, it should be mentioned that when setting up the OpenSSH server on a new host for the first time, you can also choose to have ECDSA host keys generated for the server, rather than the standard RSA or DSA keys.
I don't recommend wiping your existing RSA or DSA keys in favor of ECDSA quite yet. Plenty of OpenSSH and proprietary SSH servers exist that do not support ECC. Thus, your newly generated ECDSA key won't work, even if you copy it to the authorized_keys file. However, if you have the servers that support it, then why not give it a go, and see what you think?