There's more...

So, what happens if you remove all the host keys from the server?

This is what you get:

[vagrant@centos2 ~]$ sudo rm /etc/ssh/ssh_host_*
[vagrant@centos2 ~]$ logout
Connection to 192.168.33.11 closed.
[vagrant@centos1 ~]$ ssh  192.168.33.11 
ssh_exchange_identification: read: Connection reset by peer

At this point, you can either re-provision your VM, or log on via the console and generate new keys.