SSH No Longer Working After Sierra Update

The first time you connect to a server, you are prompted to accept the fingerprint for the host you are connecting to. The fingerprint is a combination of a digital signature, the host name and the IP address of the server. When you do accept, the fingerprint is saved in ~/.ssh/known_hosts as being a "trusted" host.

For some reason, the server's fingerprint has changed since the first time you connected to it. This may be because it is not the server you expect it to be, for example when your request is being intercepted and redirected to a different server. Hence the security warning. The explanation might also be less malicious, for example when the server was replaced/reinstalled without restoring it's previous digital signature, or when the IP address has changed.

If despite the security warning, you still trust the server you are connecting to, you should open ~/.ssh/known_hosts and look for the line starting with the address of the server you are connecting to. Remove the entire line and save your changes, then reconnect to the server. The first time you connect, it should again prompt you to accept the updated fingerprint, after which you should have no more troubles connecting to that host.

The reason why it would work with sudo is because in those conditions you are running it as a different user (root), and each user has it's own known_hosts file (for root this is located at /private/var/root/.ssh/known_hosts). root may have never recorded the previous fingerprint of that host, and therefor has no way of comparing it to the current one, and no reason to distrust the server.

It looks to me like you're using the wrong remote IP address in your tunnel. You should be using -L 5901:127.0.0.1:5900 ....

It's important to realize that the destination IP for the tunnel is where the remote (server) computer forwards the connection to, so 127.0.0.1:5900 means it connects to port 5900 on the server itself.

It looks like you're using ssh -L 5901:PublicIPofServer:5900 ..., which makes the server try to connect to port 5900 on its own public IP. But that's actually the WAN IP of the router the server's behind, so unless that router forwards port 5900 to the private IP of the server (in which case you wouldn't need the SSH tunnel) AND the router supports NAT loopback (aka hairpin NAT), this won't work.