After trying to start ssh on a fresh VPS, I got the following error message:

sh-3.2# service sshd start
Starting sshd: Could not load host key: /etc/ssh/ssh_host_rsa_key
Could not load host key: /etc/ssh/ssh_host_dsa_key
Disabling protocol version 2. Could not load host key
sshd: no hostkeys available — exiting.
[FAILED]

The fix is simple, just run the following commands, then try and start it again and it should work

ssh-keygen -t rsa1 -f /etc/ssh/ssh_host_key -N “”
ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key -N “”
ssh-keygen -t rsa -f /etc/ssh/ssh_host_rsa_key -N “”