There's a new SSH trojan going around—or at least, I think it's new, and I haven't seen it be described anywhere else. (Please correct me if I'm wrong.) I've seen it in use in more than one breakin on more than one continent, though, so my guess is that it's something that's sold on the usual black market. In lack of a name, I've chosen to call it “Ebury” out of rather arbitrary reasons.
Ebury replaces /usr/sbin/sshd, /usr/bin/ssh and /usr/bin/ssh-add with its own versions (and in some but not all cases, it seems .list files are edited so as to fool debsums). The new versions seem to be custom-compiled for the machine, with different architectures and encryption keys. The new versions don't link against libwrap and libselinux, so you lose /etc/hosts.deny and the likes.
On the other hand, it has quite some nasty extra functionality. In particular, all three binaries will record all passwords and passphrases you give them, and store them in shared memory. If you look at the output of “ipcs”, a typical example is this:
------ Shared Memory Segments -------- key shmid owner perms bytes nattch status 0x0000cf39 98304 root 666 2097220 0 0x0000cd38 131073 root 666 2097220 0
The interesting part is that the segments are read/write for everybody, which is normally not what you want. Also, the size (2097220 or 2097224 bytes, depending on architecture) is a telltale sign.
When storing passwords to this memory, a DNS packet (or, something vaguely resembling a DNS packet) is sent out to an external server with the right information. DNS usually goes under the radar, unfortunately, but if you see machines suddenly sending packets on UDP port 53 to external hosts and those are not your usual DNS servers, beware.
Also, the trojaned sshd contains backdoors for logging in without a password, and for decrypting and outputting the information in the shared segments. Backdoored logins don't log anything to auth.log, and outputting the list of captured passwords empties the segment in the process. I don't know how the trojan spreads, but it appears to be either SSH bruteforcing or using the password list captured from other machines. In other words, even if you're patched, you could be infected if your password has been typed on a compromised machine!
I've made a small, heuristic detector which also attempts to do a chosen-plaintext attack against the (very weak) encryption of the shared-memory segments. You can find it at [http://storage.sesse.net/ebury.tar.gz].
TL;DR: Check your sshd checksums, and run “ipcs” to see that there are no segments about 2097220 bytes long.