Ssh – How to keep SSH’s know_hosts up to date (semi-securely)

Just to get this out in front so I am not told not to do this:

1. The machines in question are all on a local network with little to no internet access (they aren't even well connected to the corporate network)
2. Everyone who has the ability to setup a man-in-the-middle attack already has root on the machine
3. The machines are reinstalled as part of QA procedures, so having new host keys is important (we need to see how the other machines react); I am only trying to make my machine nicer to use.

I do a lot of reinstalls on machines which changes their host keys. This necessitates going into ~/.ssh/known_hosts on my machine and blowing away to old key and adding the new key. This is a massive pain in the tuckus, so I have started considering ways to automate this.

I don't want to just blindly accept any host key, so patching OpenSSH to ignore host keys is out. I have considered creating a wrapper around the ssh command the will detect the error coming back from ssh and present me with a prompt to delete the old key or quit. I have also considered creating a daemon that would fetch the latest host key from a machine on a whitelist (there are about twenty machines that are being constantly reinstalled) and replace the old host key in known_hosts.

How would you automate this process?