ssh: Operation timed out

I'm having trouble setting ssh up properly on my new (2016) mac. I end up with the classic

ssh: connect to host xxx.xxx.xx.xxx port 22: Operation timed out

I'm moving from an older mac, both are running OS 10.11.6. The old mac was migrated from an even older (2007ca) mac so I don't want to use the migration software to update.

I need to access a linux (fedora 20) server that is behind a firewall. I use VPN to tunnel through the firewall. It is setup on my new mac and verified by that the server I need to connect to actually answers ping.

Accessing the server works perfectly from my old mac.

I have tried telnet

telnet xxx.xxxx.xxx.xxx 22

and the WORKS on my old mac, but does NOT WORK on my new mac. That feels like it should narrow the problem down, but I'm not sure how. Something to do with the setup on my new mac... I suppose.

I also tried outputting more verbose data from ssh on my new mac:

ssh -v -v -v user@xxx.xxx.xxx.xxx

OpenSSH_6.9p1, LibreSSL 2.1.8

debug1: Reading configuration data /etc/ssh/ssh_config

debug1: /etc/ssh/ssh_config line 21: Applying options for *

debug1: /etc/ssh/ssh_config line 56: Applying options for *

debug2: ssh_connect: needpriv 0

debug1: Connecting to xxx.xxx.xxx.xxx [xxx.xxx.xxx.xxx] port 22.

debug1: connect to address xxx.xxx.xxx.xxx port 22: Operation timed out

ssh: connect to host xxx.xxx.xxx.xxx port 22: Operation timed out

This looks exactly the same on the old mac until I get the "Operation timed out"