我有同样的问题，因为我没有公钥，所以我做到了：

heroku keys:clear
heroku keys:add

这将生成公钥，然后工作正常

如果您已上载密钥，请尝试删除密钥，然后重新上载它有一把新钥匙。

 heroku keys:remove //removes the existing key
 ssh-keygen -t rsa //generates a new key in ~/.ssh folder
 heroku keys:add    //uploads the new key, if no arguments r passed then the key generated                              
                    //in default directroy i.e., ~/.ssh/id_rsa is uploaded
 git push heroku

这应该奏效。

当TortoiseGIT安装在我的机器上时，我遇到了这个问题。将环境变量GIT_SSH从

"c:\Program Files\TortoiseGit\bin\TortoisePlink.exe"

to

"c:\Program Files (x86)\Git\bin\ssh.exe"

使用ssh-keygen和keys完成本教程：add，它起作用了！

我花了三天的时间尝试各种可能的组合，试图让它发挥作用——我最终尝试了制作DSA密钥，结果成功了。

如果不适合您，请尝试DSA而不是RSA。

（我使用的是Ubuntu 11.10、ruby 1.8.7、heroku 2.15.1）

我必须这样做：

$ ssh-keygen -t rsa  
$ heroku keys:add  

然后它奏效了：

$ git push heroku master  

我重新安装了heroku工具带，它工作了。