Eu finalmente encontrei o que estava causando o problema. Isto foi devido ao meu roteador bloqueando mensagens TCP keepalive quando eu conectei sem fio (vai figura).
ssh my_server -o TCPKeepAlive=no
resolveu todos os meus problemas. Yay!
Da documentação:
TCPKeepAlive
Specifies whether the system should send TCP keepalive messages
to the other side. If they are sent, death of the connection or
crash of one of the machines will be properly noticed. However,
this means that connections will die if the route is down tem-
porarily, and some people find it annoying. On the other hand,
if TCP keepalives are not sent, sessions may hang indefinitely on
the server, leaving "ghost" users and consuming server resources.
The default is "yes" (to send TCP keepalive messages), and the
server will notice if the network goes down or the client host
crashes. This avoids infinitely hanging sessions.
To disable TCP keepalive messages, the value should be set to
"no".