Mark wrote a comment on my note about nssh:

A warning about 'StrictHostKeyChecking no' by default. I had the same thought as you did, and tested the behavior. When set to 'no', ssh will connect anyway if the host key changes and you're using public key auth (it will print a warning, and disable password based auth however), which doesn't prevent a man in the middle attack if the person has access to your public key (which it's very likely they will have).

I looked at that and said 'that can't be entirely right; access to your public key shouldn't make any difference'. But intuition is a bad guide to security and cryptography, so I went off to read up on the SSH-2 protocol RFCS to see for myself (or at least skim through them). The result was interesting and comes to a stronger conclusion than I was expecting: I believe that if you use public key authentication you're probably immune to man in the middle attacks.

The SSH 'protocol' is actually three pieces: a transport protocol that creates the basic encrypted session, an authentication protocol, and a connection protocol. When a SSH connection starts, the transport protocol negotiates a shared session key and a session identifier and in the process validates the host key of each end. Although I'm not qualified to say if it's fully successful in this, the transport protocol attempts to make sure that the session identifier can't be fully controlled and set by either end; it's always a blend of things from the server and the client.

Once the transport is running, SSH attempts public key authentication in the traditional way: it assembles a known block of data, signs it with the private key, and sends the signature to the server to be verified. Note that the client does not send the block of data, just the signature. This known block of data includes the session identifier. Thus, in order to pass user authentication with the server, you need a signature that uses the session ID of your connection to the server. Unless you know the victim's private key (not just their public key), you need to somehow force the client's connection to you to wind up with the same session ID as your connection to the server so that you can simply relay the client's user authentication message to you on to the server.

I can't categorically say that a man in the middle can't arrange identical session IDs for each connection; I don't know enough cryptography (and understand the SSH protocol that well). However, part of the session ID comes from the public Diffie-Hellman key parameters and my best understanding is that you cannot feasibly recover a D-H key from the public parameters alone. It sure looks like a MITM must do this in order to arrange for identical session IDs; it must present the client's public parameter to the server (instead of its own) and the server's public parameter to the client (instead of its own), yet still wind up with its own valid keys for both connections.

(You can of course trivially impersonate a server (at the SSH level), even without knowing someone's public key. All you have to do is accept whatever signature they send you without even checking it, because the whole user authentication step has no effect on the session encryption; it's only used by the server to decide whether or not to give you access. But this is a lot less dangerous than a genuine MitM attack.)