To summarize, you've observed three different behaviors when connecting from inside your network:
- From machine A, you can't even establish an SSH connection because the client and the server don't support matching protocol options.
- From machine D, the client rejects the connection because of a host key mismatch.
- From machine M, the SSH connection is established but then user authentication fails.
All of this indicates that you aren't reaching the host that you thought you were reaching. As several people have already remarked in comments, when you access your external IP address from inside the network, you're in fact reaching your router. (More precisely, you're reaching your NAT appliance — for a home or small office network it's just one box doing routing, NAT, and possibly being a modem as well.) Furthermore:
- The fact that you can't establish a connection from A suggests that the server you're reaching only supports a small subset of the available options (common on routers) and that it hasn't been updated in a while (again, common on routers) —
- The fact that D detects a host key mismatch clearly shows that this isn't the host you were looking for.
- M has no problem connecting because it still supports the deprecated protocol and you'd never connected to your desired server from that client so it didn't see any mismatch. You should remove the corresponding public key from the
known_hosts file (
ssh-keygen -R 36.xxx.xx.xx) or else you'll get an error if you try to connect to your desired server.
When you attempt to connect to your external IP address from the inside of your network, what happens depends on how the NAT appliance is configured. It's common that it sees a connection request to one of its IP addresses, and treats that as a connection to itself. That depends how NAT is configured; typically it's configured by interface, so incoming connection requests coming from the outside get translated according to the incoming redirection rules but connection requests coming from the inside are only translated if they actually go outside, not when they end at the NAT appliance.
It's common for home routers to offer an SSH interface, and there's no particular reason to disable it. Even the deprecated protocol is no big reason to worry: the attack against it is only “within theoretical range” — best avoided but not immediately broken. The fact that the software is old is cause for concern however; it might have other unpatched security vulnerabilities. Make sure that your router isn't listening to anything on its outside interface at a protocol level above TCP (i.e. let it do NAT but make sure that SSH, web interfaces etc. are restricted to internal IP addresses). And if you have wifi or if you don't trust your physical network, tighten internal connections as well.