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

heroku keys:clear
heroku keys:add

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

我必须这样做：

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

然后它奏效了：

$ git push heroku master  

上面给出的答案确实有效，但我发现我需要做一些额外的步骤才能奏效。

我删除了所有id_rsa*文件，并使用本指南生成了一个新的SSH。然后，我销毁了heroku应用程序。删除了~/.heroku/credentials文件。“heroku create”命令（由于凭据文件已删除，它将提示您输入电子邮件/密码。最后键入“heroku-keys:add”，它将上载默认的~/.ssh/id_rsa.pub文件。它起作用了！好YMMV，但我真的希望这能对我有帮助，因为我一整天都在努力解决这个问题！哈哈

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

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

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

如果您是windows用户，这里的其他解决方案可能无法解决您的问题。

我使用的是Windows 7 64位+Git-1.7.7.1-review20111027，解决方案是将我的密钥从C:\users\user\.ssh复制到C:\Program Files（x86）\Git\.ssh。这是Git客户端在推送到heroku时查找密钥的地方。

我希望这有帮助。

dmajkic的解决方案最终帮助了我：

对于Windows用户，这可能意味着：git客户端找不到您的密钥。检查c:\Users\UserName.ssh\和！环境变量HOME=c:\Users\UserName\