TL;DR
The error, Permission denied (publickey) might be fixed by creating the .known_hosts file. Check if the file exists, if not simply touch ~.ssh/.known_hosts
A little while ago I ran into this error:
Cloning into 'dev'... Permission denied (publickey). fatal: Could not read from remote repository. Please make sure you have the correct access rights and the repository exists.
I was a little confused because I just created the keys so I knew they existed and also added the public key to my github account of which I got the confirmation that it was added successfully.
I checked the .ssh directory if the keys existed. Checked the key if it matched with the one in my account and tried again. Still no access.
Maybe something messed up my known hosts file, it should help if I delete the line for github.com and try to reconnect.
Enter the .ssh dir and check .known_hosts… File does not exists… weird…
Turns out all I had to do was creating the .known_hosts file and everything started working like a charm. Never had this problem before and I’ve been using git for quite a while now.