Isso parece perigosamente próximo de uma questão de compra, que é proibida pelo SF (e outros sites da SE, aparentemente) pelo FAQ. Você também não menciona qual sistema operacional será executado nos servidores em nuvem; mas vou seguir em frente e assumir que é o Linux.
Dito isso, minha primeira preferência seria pelo IPSec, já que ele é incorporado ao Linux, é incrivelmente robusto e está bem integrado no nível da rede (para que você não precise mexer nas tabelas de roteamento). Não haverá problemas com a autenticação, pois tudo é feito com chaves ou certificados pré-compartilhados. Ele se integra bem com iptables firewalls. Ele recupera bem após interrupções de rede estendidas. Ele aparece automaticamente no momento da inicialização por meio dos scripts padrão /etc/rcN.d . Com os túneis IPSec no lugar, os aplicativos só precisam lançar pacotes nos endereços IP; a criptografia acontece way na pilha a partir daí.
Em caso negativo, OpenVPN. É mais complexo que o IPSec, mas compartilha muitas das mesmas vantagens.
Se isso não acontecer, os túneis ssh devem ser - mas você estará sempre correndo atrás deles quando as interrupções da rede tiverem caído. Eu prefiro ter (ainda mais) trabalho de canal radicular do que isso com túneis ssh.