Relearn or overwrite old know_hosts with new host keys
Use this command
ssh-keygen -R hostname
For example,
ssh-keygen -R server2.mycompany.net
This will allows changes to known_hosts to occur which will no longer trigger the host authenticity warning.