One good thing to note is that any VM image using cloud-init (a package for debian/rhel systems) should automagically generate a new host_key set for any new sy

One good thing to note is that any VM image using cloud-init (a package for debian/rhel systems) should automagically generate a new host_key set for any new system image. Basically if you build a system image for EC2 or any system that uses the EC2 data format (like Openstack) for host instantiation, then you should install cloud-init. It would prevent something like this.