At least they have a very clear error message so you know what is going on.

> git@github.com: Permission denied (publickey). fatal: Could not read from remote repository.

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

Just rolled new keys and though I'm going crazy that it's not working