Допустим, мой приватный gpg ключ украли...

Смотря какая фраза. Если простая, тогда можно взломать, но если сложная (где-нибудь 15-20 случайных символов), тогда это непросто.

В любом случае, если ключ украли, отзывать, чтобы люди им больше не пользовались, и генерировать новый.

Если злоумышленник подберёт фразу, то всё сможет расшифровать. В PGP нет (P)FS.

Что тогда делать?

Искать адвоката, в лучшем случае. Стать на путь «Большего Стэна» в худшем случае. Его ведь чаще всего только локально можно достать.

rtfm: revocation certificate

Что тогда делать?

Уругвай, Боливия, Аргентина.

бггг чо? он своих лоли на харде шифруед какой ревокейшн.