This was taken from https://wiki.archlinux.org/index.php/SSH_keys#Ed25519
The Windows SSH client PuTTY does not support ECDSA as of March 2016. One needs a PuTTY development snapshot to connect to a server that uses only ECDSA keys.
Ed25519 was introduced in OpenSSH 6.5: "Ed25519 is an elliptic curve signature scheme that offers better security than ECDSA and DSA and good performance". Its main strengths are its speed, its constant-time run time (and resistance against side-channel attacks), and its lack of nebulous hard-coded constants. See also this blog post by a Mozilla developer on how it works.
Ed25519 key pairs can be generated with:
# ssh-keygen -t ed25519
There is no need to set the key size, as all Ed25519 keys are 256 bits. Also, they rely on a new key format which "uses a bcrypt-based key derivation function that makes brute-force attacks against stolen private keys far slower".
For those reasons, compatibility with older versions of OpenSSH or other SSH clients and servers may prove troublesome.