Turn off strict checking of ssh keys

The great feature HostKeyAlias solves your problem:

ssh -o HostKeyAlias=hostkeyalias__vm_2013-05-11_07 user@host

creates an entry hostkeyalias__vm_2013-05-11_07 (without IP) in known_hosts. Of course, you could write a script or shell function which sets this value before each ssh call. Or you use a shell variable:

HOSTKEYALIAS=hostkeyalias__vm_2013-05-11_07
ssh -o HostKeyAlias=$HOSTKEYALIAS user@host

and change $HOSTKEYALIAS whenever the VM is changed. From time to time the old entries should be deleted from known_hosts.

create ~/.ssh/config with the contents:

Host *
    StrictHostKeyChecking no

Alternately, you can create an alias for ssh to:

ssh -o StrictHostKeyChecking=no

The problem is that ssh presumes a 1-to-1 mapping between IP addresses and hosts. We need to break that mapping only for the IP addresses of your cloud servers.

The Solution

Add the following stanza to your ~/.ssh/config file.

# Disable HostKey checking for servers which frequently change keys
Host 172.16.24.32  172.16.24.33  172.16.24.34
    UserKnownHostsFile /dev/null
    StrictHostKeyChecking no

Just change the IP addresses and you are done.¹

Optional: An alternative for IP address ranges

If you'd like to apply this to a netblock, such as 192.168/16, you can use wildcards like so:

# Do not keep HostKeys for internal networks.
Host 10.*.*.*  192.168.*.*
    UserKnownHostsFile /dev/null
    StrictHostKeyChecking no

Optional: Using hostnames

The original question mentioned IP addresses, but you can, of course, use hostnames instead. For example, this would match ssh instance32.vm.yoyodyne.com:

Host *.vm.yoyodyne.com
    UserKnownHostsFile /dev/null
    StrictHostKeyChecking no

If you want to use both hostnames and IP addresses, you'll need to explicitly specify both as SSH does not match on the resolved IP address. For example, if you have ssh ourvm.local as a shortcut for ssh 192.168.1.53:

Host 192.168.1.53  ourvm.local
    UserKnownHostsFile /dev/null
    StrictHostKeyChecking no

Caveat

Be cautious when circumventing ssh's security model. In particular, double check that your wildcards do not match any genuine servers whose HostKeys will not be changing.

---

¹ ^{Why /dev/null? I'm throwing the KnownHosts data into the bit bucket because only setting StrictHostChecking no removes the warning, but still refuses to connect. This is silly, so I presume OpenSSH will eventually change the behavior or add a new option. If and when a better solution comes around, I'll update this answer.}