Как (правильно) шифровать данные и хранить ключи на облачном сервисе?
Обычно облачный провайдер продает не только виртуалки и хранилища но еще и сервисы безопасного хранения ключей. Например для Microsoft Azure - это KeyVault https://azure.microsoft.com/en-us/services/key-vault/

Для amazon - это KMS https://aws.amazon.com/kms/

Берите и используйте.
Если говорить про вектор атаки - однократный физический доступ злоумышленника к серверу, то хранить критичную информацию только в оперативной памяти, обфусцированной (чтобы дамп памяти было сложно анализировать) и вводить загружать вручную только в момент включения/перезагрузки машины

Обычно сама информация в памяти зашифрована например паролем, и вот этот пароль уже вводится пользователем, возможен вариант с многоуровневым шифрованием, когда пароль расшифровывает набор ключей для шифрования а они в свою очередь дают доступ к всей базе паролей (сама база паролей зашифрованной может лежать где угодно)

Один из способов - загрузочное устройство, которое физически подключается к серверу при включении/перезагрузки и содержит в себе физическую клавиатуру, код загрузчика (если linux то банально установленный grub и vmlinuz и initramfs) и необходимые ключи шифрования, а сами данные уже полностью зашифрованные хранятся на сервере. Так же разделяют собственно расшифровку ключей и физическое подключение устройство, доверив последнее другому сотруднику (его задача контролировать что железо не подменено и следить за закрытием сейфа и помещения) а ввод пароля проводится по сети другим.

В этой схеме сервер все равно нужно защищать физически от доступа злоумышленника, так как подменив железо можно так или иначе получить доступ к данным (просто с отдельным носимым загрузчиком эта атака становится очень дорогой).

p.s. это не защитит данные от других векторов атаки, например через уязвимости в софте! но для этого стараются разделять операционными системами хранение и обработку данных (точнее разделение на микросервисы с виртуализацией и разграничением доступа для каждого, чтобы взлом одного не дал ничего кроме того чем этот модуль занимается).

плюс по мелочи, типа нестандартное окружение, в котором нет привычных инструментов, не нужных сервису (например злоумышленник может очень огорчиться, если сервис nodejs не будет уметь запускать sh скрипты, не будет python и т.п.)