Sorry for replying again, but the thing all these logs seem to have in common is that all of us are ssh'ing to a private network, instead of a "public IP" (sorry for the missnomer): michelem and me are trying to connect to a 10.*.*.* IP and AndrewLawrence is doing the same for a 192.168.*.*, typical for home LAN's.
However, connecting to the Debian box (it has an IP reachable from everywhere) is as fast as ever.
Sorry for replying again, but the thing all these logs seem to have in common is that all of us are ssh'ing to a private network, instead of a "public IP" (sorry for the missnomer): michelem and me are trying to connect to a 10.*.*.* IP and AndrewLawrence is doing the same for a 192.168.*.*, typical for home LAN's.
However, connecting to the Debian box (it has an IP reachable from everywhere) is as fast as ever.