I had a similar problem with keys. Ok, this is what I did.
Check the status of your keys with
heroku keys
It displays a list of keys that are added to the hero. You can always generate new keys and add them to the hero.
ssh-keygen -t rsa
Creates a new key.
heroku keys:add
Adds keys to the hero. Before adding to it, the available keys that you can add are listed. Enter the option and the key is added to the hero.
This article may be helpful. If this does not work, there is a problem with ssh. Try ssh localhost and see if ssh works.
Maddy source share