we once had a little Ed script called "Offending" which would accept the ssh connection failure line

  Offending key ...

and edit the failing key out of the known_hosts file.

extremely useful with bazillions of fresh virtual guests with well known static IP. you simply cut and paste the "Offending key" line into the shell and the ed script does it's magic.