Debian 7 minimal OpenVZ template was applied to a VPS, but VPS was not accessible, no login prompt, only ping worked. SSH service was running and listening at port 22

vzctl enter VMID

tail /var/log/auth.log
Jun 14 10:10:01 vkpwgmxv CRON[1646]: pam_unix(cron:session): session opened for user root by (uid=0)
Jun 14 10:10:01 vkpwgmxv CRON[1646]: pam_unix(cron:session): session closed for user root
Jun 14 10:30:48 vkpwgmxv sshd[1649]: error: Could not load host key: /etc/ssh/ssh_host_rsa_key
Jun 14 10:30:48 vkpwgmxv sshd[1649]: error: Could not load host key: /etc/ssh/ssh_host_dsa_key
Jun 14 10:30:48 vkpwgmxv sshd[1649]: error: Could not load host key: /etc/ssh/ssh_host_ecdsa_key
Jun 14 10:30:48 vkpwgmxv sshd[1649]: fatal: No supported key exchange algorithms [preauth]
This command made from within VPS fixed it:
/usr/bin/ssh-keygen -A
service ssh restart