Don't use SSH in a trust-on-first-use configuration in that situation. There are two other modes to use. Either DNSSEC with SSHFP fingerprints, or sign your ho

Don't use SSH in a trust-on-first-use configuration in that situation. There are two other modes to use. Either DNSSEC with SSHFP fingerprints, or sign your host keys with a CA key that you install on all your machines. A decent configuration management tool could also keep known_hosts up to date, but it tends not to be worth the trouble. Do the above first.