This problem was messing with me for a few days.
This might help.
1) Find out what keys you have in Heroku now.
$ heroku keys
=== 1 key for [email protected]
ssh-dss AAAAB8NzaC...DVj3R4Ww== [email protected]
2) Build a ~/.ssh/config file:
$ sudo vim ~/.ssh/config
Edit with this info
Host heroku.com
Hostname heroku.com
Port 22
IdentitiesOnly yes
IdentityFile ~/.ssh/ssh-dss # location and name of your private key
TCPKeepAlive yes
User [email protected]