Connect them to a private zerotier network (https://www.zerotier.com/#try_zerotier) it's free and you can bind sshd just to the zt0 interface. Instant access from anywhere.

Sounds like yet another hosted/subscription based service.

You can use your own server if you prefer. Otherwise it's hosted. No subscription needed if you're not using massive networks.

That sounds a lot harder than solving the original problem.

I may be biased, but I put zerotier on lots of hosts these days. Whether it's home raspberrypi for remote access, or vps to get all administration off the public network, or sometimes just as a VPN replacement for stuff like replication. It's pretty much fire and forget.

You can install TOR on the machine and use it for NAT traversal, by making SSH available through a hidden service. Latency is a bit high but it's easy to set up and connect to.