VPN-сервер поднимите на VDS, пусть искомые машины к нему подключаются при старте автоматически, для надёжности можно в крон на них скриптик запихнуть, скажем раз в минуту проверять статус VPN подключения, если упало, попытаться переподключиться. OpenVPN отлично подойдёт, но это не принципиально.
Web терминалы в целом имхо штука небезопасная, но вот GateOne показался неплохим в этом плане, использует SSL, авторизацию, при необходимости ключи тоже можно прикрутить. Ну а дальше в браузере
https://VDS, там ssh://<vpn адрес клиента> и вуаля.
