It is also possible to run into this issue in various other ways, especially when dealing with Windows which may have several implementations of SSH tacked on to it.
I ran into this when ssh'ing into a Windows 10 machine that was running SSH server under Cygwin. When you run
ssh from that prompt, it runs the cygwin version of ssh, which uses ~/.ssh to store the ssh files --- under cygwin that is /home/username.
However, if you run
git from that same prompt, and Git has been installed via Windows (which in my case it had been), it uses the ssh files from C:\Users\username.ssh.
Normally you run
ssh hostname to cache the host key for git, but in this case it does not work, since there are different known_hosts files.
Once I copied the key from one known_hosts file to the other, the
git commands worked fine.