A primeira coisa que vem à mente é o fato de que a transferência de dados dentro e fora do S3 é bastante cansativa. Se você está fazendo backup com freqüência (como deveria), os custos podem ficar fora de controle apenas com as taxas de transferência. Dito isso, para responder à sua pergunta, os backups devem ser executados em um servidor separado e reforçado, cuja única tarefa na vida é realizar backups. Não há apache, acesso remoto apenas via SSH com autenticação de chave, etc. Se você fizer essas coisas e garantir que apenas poucas pessoas selecionadas tenham acesso ao servidor, suas chaves devem ser bastante seguras. Se você é realmente paranóico, você pode criptografar o arquivo que contém suas chaves - o problema com essa abordagem é que ele exige que você insira sua senha toda vez que a tarefa de backup for executada. Isso provavelmente não é algo que você deseja se inscrever, correto?
Depois de ouvir sobre seu orçamento restrito, não posso deixar de pensar que seria melhor que você alterasse sua estratégia de armazenamento. Não tenho certeza de qual é a sua situação de servidor, mas você poderia, talvez, hospedar os arquivos localmente no servidor e depois usar o S3 para backups? Existe um ótimo script de backup chamado duplicidade que pode executar backups incrementados, criptografados e incrementais para o S3 (entre vários outros tipos de armazenamento de back-end). / p>
[Editar] Se você acabar hospedando-se no S3 e fazendo backup no disco local, parece que há um "If-Modified-Since" cabeçalho na API do S3 que ajudará na realização de backups incrementais. Para backups como este, é provável que você precise homebrew algo, embora não seja muito difícil. Basta usar SimpleDB / BerleleyDB / etc para armazenar meta informações sobre quais arquivos você fez backup junto com um ponteiro para onde eles residem no disco. Manter as meta-informações em um banco de dados também fará um rápido trabalho de verificação de backups, além de criar relatórios sobre tarefas de backup.