Assumindo que o problema NÃO é a configuração em suas máquinas Linux, a conexão pode estar bloqueada por algum firewall na rede.
Eu encontrei esta solução ("reversa SSH"), que funciona, deixando sua namorada SSH para você primeiro e, em seguida, usando esta conexão para o ssh de volta para ela:
A configuração simples (onde sua namorada precisa fazer algum trabalho a cada vez que você quiser se conectar):
# first SSH from your girlfriend TO your Laptop
ssh -f -N -R 10000:localhost:22 your_username@ip_address_of_YOUR_laptop
# now ssh to port 10000 on your laptop, which will actually connect you to port 22 on your girlfriend's laptop.
# Use the user information that you would use to log into your girlfriend's computer.
ssh girlfriend_username@localhost -p 10000
No site, no link, há também uma abordagem mais completa, onde sua namorada não precisa interagir. Mas tente a abordagem simples primeiro para ver se funciona.