Apparently openssh 6.5+ supports Ed25519 for keys now. Based my reading of this article, that sounds like a good thing.
Meawhile, OS X won’t even let me use ECDSA keys on OS X 10.9.2.
It is particularly frustrating because the man page on 10.9.2 claims that it is supported! Some weird man page build issue or something.
You can install openssh from homebrew tap, to get a newer version. For a while it was completely busted (version change broke patch required to work with osx keychain). I haven’t tried it since the tap was updated yet though.
I wouldn’t mind a newer version in FreeBSD 10 base either. :/
Did they change the defaults? Do you need to edit sshd_config?
Note that ECDSA host keys are still the preferred default.