After upgrade to new version of SSH you may experience the following problem with return code 255:

Permission denied (public key).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights and the repository exists.

This happened to me after upgrade from Linux Mint 17 to 18.

How to diagnose the problem?

Run following command:

ssh -v git@github.com

You will see several lines of output and one of them is typically the reason. In my case it was:

...
debug1: SSH2_MSG_NEWKEYS received
debug1: Skipping ssh-dss key ~/.ssh/id_dsa - not in PubkeyAcceptedKeyTypes
...

DSA keys were disabled in SSH 7. Solution is to generate new key with different type, for example RSA.

ssh-keygen -t rsa
cat ~/.ssh/id_rsa.pub

Replace your key at GitHub by newly generated one. You can re-run “ssh -v” command to check whether the communication was established correctly:

PTY allocation request failed on channel 0
Hi georgik! You've successfully authenticated, but GitHub does not provide shell access.
...
debug1: Exit status 1

That’s a good sign. The connection was established and now you can try to clone a repo.