Ubuntu Networking :: Ssh Public Key Authentication Only Works When Already Logged In?

I have an ssh (OpenSSH_5.1p1 Debian-6ubuntu2) client A and a server B set up for public key authentication as described in [URL]

The problem is the following: ssh asks for a password when connecting from A to B without any other ssh session going on between A and B; but if I connect from A to B whenever there is another ssh session between A and B, either I get prompted for the passphrase I used to encrypt the private key or I get logged automatically.

I already checked permissions on B: .ssh is 700 and authorized_keys is 600. I already tried "StrictModes no" in sshd_config. Printing debug information using DEBUG3 does not any useful insight. Moreover, there is no /var/log/secure (is it supposed to be there?)

Right now the computer is far far away from my reach, but when I configured the system I noted that whenever I was locally logged to B and then ssh'ed from A to B, I was logged in without any problem; whenever I was not logged in locally I was asked for a password. Note that at that time I was using a different public/private key pair whose private part had no passphrase.

how to know exactly what cipher is ssh/sshd using for a particular session? Is there a way to know any statistics for a given session (something like the ~s option in section 5 of [URL]

P.S. 2: does the following mean that ssh is using protocol 2.0 or something different than protocol 2.0?

(..........) sshd[2606]: debug1: Enabling compatibility mode for protocol 2.0