You could use a VPN to connect to the remote network first, and then directly connect via SSH. This may or may not be possible, may or may not be what you want to achieve in the first place, but it will work.
I heavily recommend you expose as few as possible machines to the internet via port mapping! Especially if password/keyboard interactive authentication is allowed. People do have weak passwords.
Another suggestion might be to connect to your proxy machine and have it explicitly build tunnels to each and every machine you want to directly reach behind your NAT. You can either specify one (or more) SSH tunnels directly from the command line like this:
ssh -L localport:hostnameOrIPofMachineBehindNAT:remoteMachinePort yourusername@proxy.example.com
Where localport ist the port number you need to connect on your localhost that will be forwarded to the machine behind NAT, SSH tunneled through your proxy.
hostnameOrIPofMachineBehindNAT is the LAN IP or LAN DNS of the non-proxy machine you want to reach behind NAT. Often in a private IP Range like 10/8, 192.168/16 or 172.16/12.
remoteMachinePort is the port number of the service you want to connect to on the remote machine behind NAT. In case of SSH it is likely that this will be the standard port 22.
yourusername@proxy.example.com is trivial I guess.
You can then connect to your other machine like this from another local shell:
ssh usernameOnRemoteBoxBehindNat@localhost
Since a command line can easily get very long an tedious to type, it is way better to stuff all this, with as many SSH options you want, and as many port tunnelings you like into your ~/.ssh/.ssh_config file. This will reduce your typing to ssh connectionNickname and always have all the forwardings and options set automatically.
See man 5 ssh_config for an in depth explanation and list of config options you can use in ~/.ssh/.ssh_config.
Don't use a password. Generate a passphrase-less SSH key and push it to your VM.
If you already have an SSH key, you can skip this step…
Just hit Enter for the key and both passphrases:
$ ssh-keygen -t rsa -b 2048
Generating public/private rsa key pair.
Enter file in which to save the key (/home/username/.ssh/id_rsa):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/username/.ssh/id_rsa.
Your public key has been saved in /home/username/.ssh/id_rsa.pub.
Copy your keys to the target server:
$ ssh-copy-id id@server
id@server's password:
Now try logging into the machine, with ssh 'id@server', and check-in:
.ssh/authorized_keys
Note: If you don't have .ssh dir and authorized_keys file, you need to create it first
to make sure we haven’t added extra keys that you weren’t expecting.
Finally, check to log in…
$ ssh id@server
id@server:~$
You may also want to look into using ssh-agent if you want to try keeping your keys protected with a passphrase.
Best Answer
Ping working seems to indicate you have a route to internet. If you are using the ping to your VPS using its IP and ssh with the hostname is not working, try using ssh with the IP too because it may be a DNS issue.
If ping is working with the public hostname of your VPS, ssh should work the same unless there is something (firewall or proxy) blocking outgoing connections on port 22 or there is a proxy in the LAN not configured to proxy port 22 transparently (only 80 probably). If this is the case, you may be able to use ssh defining the proxy settings for the ssh connection (if the server allows it) but without knowing more it is not easy to indicate a real solution if any.
EDIT after comments:
Seeing telnet on port 80 works and not on port 22, outgoing is probably blocked on port 22 (assuming your VPS ssh server is working and listening!). I think you have a few options:
Anyways, you'll have to connect using the 3rd option to be able to change the listening port for option 2 unless you can have your VPS provider to do this for you.