I'm gonna forgot how to fix this next time I come across it, so using this gist to document the issue. This occurs on Debian 7.5 with the following package installed from testing:
openssh-server 1:6.6p1-5, which was pulled in through the
Could not load host key: /etc/ssh/ssh_host_ed25519_key
Apparently this is a bug in the debian packaging. Luckily there's a pretty great command for fixing it:
ssh-keygen -A, which will generate any missing keys. If you're running with a VM make sure you've got enough available entropy to generate those aforementioned keys. If you don't want to run the creation command for all the missing keys, then you can just run this instead:
/usr/bin/ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key -N ''.