Stash (first) clone keeps prompting for git@mydomain.com password

[Pascal]

I'm setting up a new Stash client machine (Ubuntu terminal):

• I created a repository in Stash
• Generated a new SSH key (for myname@mydomain.com) and added it to my user account. 
• I have set the global user.name and user.e-mail (to myname@mydomain.com)

Stash tells me that I can clone the repository with "git clone ssh://git@mydomain.com/ibe/ibea.git", but when I do, it prompts me for the password of "git@mydomain.com". And there I'm stuck... 

I'm guessing there is still something missing in the configuration, but what?

(BTW, I've also tried creating some local content and adding that to the Stash repo with a "git push -u origin master", but that also prompts me for the "git@mydomain.com" password).

Edit:

It seems to be related to how the Stash server is setup. When I run "ssh -i ~/.ssh/id_rsa -vT git@stash.mydomain.com" with Git debug on, I get: 

OpenSSH_5.9p1 Debian-5ubuntu1.4, OpenSSL 1.0.1 14 Mar 2012
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to stash.mydomain.com [10.1.1.120] port 22.
debug1: Connection established.
debug1: identity file /home/plindelauf/.ssh/id_rsa type 1
debug1: Checking blacklist file /usr/share/ssh/blacklist.RSA-2048
debug1: Checking blacklist file /etc/ssh/blacklist.RSA-2048
debug1: identity file /home/plindelauf/.ssh/id_rsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.6.1p1 Ubuntu-2ubuntu2
debug1: match: OpenSSH_6.6.1p1 Ubuntu-2ubuntu2 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.9p1 Debian-5ubuntu1.4
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA 9e:06:8c:d4:34:dc:6e:b7:2c:cf:d1:22:46:e5:24:af
debug1: Host 'stash.mydomain.com' is known and matches the ECDSA host key.
debug1: Found key in /home/plindelauf/.ssh/known_hosts:1
debug1: ssh_ecdsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/plindelauf/.ssh/id_rsa
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: password
git@stash.mydomain.com's password:

So, it looks like the server wants both a public key AND a password authentication. The latter should be obsolete, however. But how do I correct this?

[Pascal · Accepted solution]

Ahhh.. stupid: we have a proxy server sitting in front of our Stash server. It had no SSH port forwarding configured. After following the instructions of installing HAProxy (next to Nginx, which we're already using), everything finally worked.

[Balázs Szakmáry]

Your SSH agent (probably OpenSSH) is probably not configured correctly. It needs to have an entry in your .gitconfig, be running and have your SSH key pair imported into it. (For details of how to achieve all this, I would suggest a Google search, it depends a lot on what you are using.)

[Pascal]

I tried it on another client (OS X terminal), which has worked before with the same Stash server but another repository and that doesn't work either. This leads me to believe that there is something wrong on the server side. I have done a little debugging and found the data that I added to the question. Does that give you a clue what might be going on?

[Balázs Szakmáry]

(Wild guesses starting now.) Is there a firewall blocking a port? Does your server know the same SSH key your client is using?

[Pascal]

Thanks, very much for your assistance Balazs. See my own answer for what the problem turned out to be.

[Balázs Szakmáry]

You are welcome. You are allowed to accept multiple answers if you want to.

[Pascal]

Good question. I'm using Ubuntu on the terminal. (I'll add it to the question).

[Balázs Szakmáry]

What client are you using for creating the clone?