My server runs Karmic Koala and OpenSSH. (the version you get from apt)
I am using public keys and no passwords. When I try to connect with a correct username and a invalid keypair the login fails but I don't get a log message telling me so! Only this:
Feb 16 03:49:26 hybris sshd[3180]: Connection from port 49277
Using invalid usernames and successful logins both result in meaningful messages, so does using a wrong password, why doesn't a failed key-attempt?

I googled it and came across two similar problems:

The solution was upping the LogLevel from INFO to VERBOSE, but if I try that I still don't get a appropriate message. I even tried out DEBUG, but still no luck. (Apart from making it really hard to read the logfile...)

Am I the only one with this problem? I find it hard to believe that nobody is missing this message. An attacker could try thousands of keys without anyone ever noticing - including fail2ban.