Comment 5 for bug 375867

The code in question is bzrlib/transport/ssh.py _paramiko_auth() which does:
    if _use_ssh_agent:
        agent = paramiko.Agent()
        for key in agent.get_keys():
            trace.mutter('Trying SSH agent key %s'
                         % paramiko.util.hexify(key.get_fingerprint()))
            try:
                paramiko_transport.auth_publickey(username, key)
                return
            except paramiko.SSHException, e:
                pass

    # okay, try finding id_rsa or id_dss? (posix only)
    if _try_pkey_auth(paramiko_transport, paramiko.RSAKey, username, 'id_rsa'):
        return
    if _try_pkey_auth(paramiko_transport, paramiko.DSSKey, username, 'id_dsa'):
        return

    if password:
        try:
            paramiko_transport.auth_password(username, password)
            return
        except paramiko.SSHException, e:
            pass

    # give up and ask for a password
    password = auth.get_password('ssh', host, username, port=port)
    try:
        paramiko_transport.auth_password(username, password)
    except paramiko.SSHException, e:
        raise errors.ConnectionError(
            'Unable to authenticate to SSH host as %s@%s' % (username, host), e)

So if you have an agent, it first tries to auth with all available keys, then it tries the rsa key (if it exists) then the dsa key (same), and if it hasn't authenticated yet, it tries password auth.

I don't know where we would check to see what authentication types are supported, such that we could skip some of these checks.

It also hints that if you have an agent with a lot of keys for various hosts, it would likely slow down your connection as it tries all of them.

I believe there is a bug open about wanting to specify an exact key to use...