I encountered this issue too. But after I disconnected my VPN, it worked.
After you generated your ssh keys, there are only two files under
~/.ssh folder which are
id_dsa.pub, but after you successfully connected to a server, another file
known_hosts will be added.
Maybe you can add that file manually. But I am sorry I don't know how to generate that file.
I had the exactly same problem! I tried to clone a public git repo (using ssh) from two different computers (macs). In one computer it worked but it didn't work in another. The only difference was: in one computer I was using zsh (in this one, the clone didn't work) and in bash in another (it worked on this). When I changed from zsh to bash in the machine that didn't work and tried cloning, it worked!! :)
I don't know why. Maybe is some problem with zsh.
This solved the problem for me:
I was getting this message, even though I had followed the guide at GitHub to the letter - including adding the public SSH key to their website https://help.github.com/articles/generating-an-ssh-key/
The issue was, out of habit I had been using using sudo in front of git commands i.e. sudo git pull. The SSH that was previously generated was in my home directory but putting sudo in front of it makes it look elsewhere for the key. So using just git pull makes it look within my home directory - it works great now!