Configure um servidor OpenVPN. Todas as máquinas remotas serão clientes OpenVPN para o servidor e receberão um endereço IP da VPN (por exemplo, 10.8.0.x). Como eles são clientes, você não se importa com o endereço IP público. Além disso, os clientes não precisarão abrir portas em seus roteadores para permitir o tráfego, já que eles farão conexões de saída com o servidor VPN.
Para chegar a qualquer uma dessas máquinas, basta enviar o ssh para o endereço IP da VPN. O daemon ssh não é exposto ao público, já que ele pode escutar somente na rede VPN.
Você não precisa executar o servidor OpenVPN no seu local; você pode configurar algo como uma instância do Amazon EC2 em, digamos, o nível gratuito para testar isso para ver se funciona para sua situação. Você provavelmente desejará um IP estático para o servidor; você pode se safar com algum tipo de travessuras, mas não para qualquer configuração real.