This issue has haunted me for years and yet it is so easy to fix.
Offending key for IP in /home/<USERNAME>/.ssh/known_hosts:<NUMBER> Matching host key in /home/<USERNAME>/.ssh/known_hosts:<ANOTHER_NUMBER>
The problem lies in that there are 2 keys for the host you are trying to reach. One key is old and one is good.
- Edit the /home/<USERNAME>/.ssh/known_hosts file
- Delete line number <NUMBER> (the line with the old key) from the file.