There is a file called known_hosts, typically in the user directory
~/.ssh/ - this contains the keys that ssh and other services use to authenticate remote machines that you connect to.
If the key for a particular server has been updated for example during an update of the OS then a new key for that server will be generated on that server. Since this conflicts with the stored key on your machine ssh will ask if you still trust that machine.
The first time you connect to a machine ssh will ask you if you trust that key. If you do then that key is copied to the known_hosts file for that user.
Look in the known_hosts file and remove the entry for the remote machine. Now when you connect you should be asked to accept the new key. By moving the file, you will probably have triggered the creation of a new known_hosts file for the first key that you import and will have lost the records of the other machine you may have connected to.