We have a solution for this at work where we use SSH host certificates signed with a known CA to get rid of this problem. If you are not familiar with ssh certificates you can read about it in the ssh-keygen manual and also there is a lot of nice guides out there:
The cloud part
In order to have the ssh host keys unique and generated at the host we have the private host CA key stored in the images we use. When the image boots the first time sshd generates new keys and then we have a "firstboot" script that basically does this:
- Signs the host keys with SSH CA private key
- Removes the SSH CA private key
- Restarts sshd.
Then all you have to do on your side is to trust this single CA key by adding it to your either personal or global known_hosts file. You will now be able to log in to the machines without and having them automatically trusted.
This may give you some security concerns because the CA is available inside the image at first boot, but it works for us because we have very good control over the infrastructure and we think its good enough to remove it once the certificates are generated.
Possible alternative solution using SSHFP
Another solution that just came to mind is the use of SSHFP records. If you have a DNSSEC signed zoned you could have the VMs report their key by some method to your DNS server and then publish their keys in DNS using the SSHFP record type. The OpenSSH client will trust these records if the zone is signed. I have writted a short guide on this: