There seems to be a bit of a meme here...
I have a set of computers that I frequently reinstall for testing purposes.
The "zomg! The host key has changed!" gets very tiresome very quickly.
Host reinstallalot
UserKnownHostsFile /dev/null
StrictHostKeyChecking no