wrong passphrase 3 times: git doesn't ask for passphrase anymore

Question

I wanted to push on a remote git repository. I typed the wrong passphrase three times. I have created a new ssh key and registered the new public key on the repository server. But the ssh agent doesn't prompt for the passphrase. It just keeps telling me:

Permission denied (publickey). fatal: Could not read from remote repository.

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

How can I solve this problem under ubuntu?

Edit

As it was suggested, I tried ssh-add

sadik@sadix:~$ cd .ssh/
sadik@sadix:~/.ssh$ ls
config  github_rsa  github_rsa.pub  id_rsa  id_rsa.pub  keys.zip  known_hosts
sadik@sadix:~/.ssh$ ssh-add 
Enter passphrase for /home/sadik/.ssh/id_rsa: 
Identity added: /home/sadik/.ssh/id_rsa (/home/sadik/.ssh/id_rsa)
sadik@sadix:~/.ssh$ 
sadik@sadix:~/.ssh$ cd
sadik@sadix:~$ cd some/git-repo/
sadik@sadix:~/some/git-repo/$ git push -u bitbucket master
Permission denied (publickey).
fatal: Could not read from remote repository.

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

I should add that this git repository has been cloned from github (not owned by me). I want to push it on my private repository on bitbucket. I don't know whether this can lead to permission problems, but my first problem is that ssh does not prompt for a passphrase. Even after reboot or log out.

Edit

As Jakuje kindly suggested I entered the command GIT_SSH_COMMAND="ssh -vvv" git push -u bitbucket master to get the client logs. This is the end of the output:

debug3: preferred gssapi-keyex,gssapi-with-mic,publickey,keyboard-interactive,password
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/sadik/.ssh/id_rsa
debug3: send_pubkey_test
debug3: send packet: type 50
debug2: we sent a publickey packet, wait for reply
debug3: receive packet: type 51
debug1: Authentications that can continue: publickey
debug1: Trying private key: /home/sadik/.ssh/id_dsa
debug3: no such identity: /home/sadik/.ssh/id_dsa: No such file or directory
debug1: Trying private key: /home/sadik/.ssh/id_ecdsa
debug3: no such identity: /home/sadik/.ssh/id_ecdsa: No such file or directory
debug1: Trying private key: /home/sadik/.ssh/id_ed25519
debug3: no such identity: /home/sadik/.ssh/id_ed25519: No such file or directory
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
Permission denied (publickey).
fatal: Could not read from remote repository.

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

For whatever reason it searches for a pubkey id_dsa, so I copied id_rsa to id_dsa and tried it again. Now it prompts for a passphrase! But ... when I enter the wrong passphrase, it asks me again. When I enter the correct one, it says permission denied.

$ git push -u bitbucket master
Enter passphrase for key '/home/sadik/.ssh/id_dsa': 
Enter passphrase for key '/home/sadik/.ssh/id_dsa': 
Enter passphrase for key '/home/sadik/.ssh/id_dsa': 
Permission denied (publickey).
fatal: Could not read from remote repository.

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

1. What's wrong with the permissions?
2. Why is it looking for id_dsa instead of id_rsa?

Answer 1

Things look complicated enough that it may be worth starting all over:

1. Remove all the keys in ~/.ssh that you don't need (if there are keys that you want to keep, consider moving them to a different directory for now).
2. If ~/.ssh/config exists, check that it doesn't have suspicious lines.
3. If you are using ssh-agent, remove all keys using ssh-add -D. Check that there are no keys using ssh-add -l. If you see any output, you are suffering from this bug. Log out, log in, and verify that ssh-add -l produces no output.
4. Run ls -al ~/.ssh and check that there are no keys there.
5. Create a new key using ssh-keygen. Press enter when it asks for the output file to use the default, then type the passphrase twice.
6. Run ls -al ~/.ssh and check that id_rsa and id_rsa.pub exist.
7. Remove existing keys from Bitbucket.
8. Add the contents of ~/.ssh/id_rsa.pub to Bitbucket.
9. Test the connection using ssh -T [email protected]. If it fails, post the output of ssh -vvv [email protected].
10. Check that git commands works.

Why is it looking for id_dsa instead of id_rsa?

SSH tries several keys until it finds one that works. It tried id_rsa, the key was rejected, so it went on to try id_dsa.

Credit to @Leon for mentioning ssh-add.