Quando postei meu comentário, não tive tempo para uma resposta mais abrangente. Aqui está.
What can I do?
Você pode solicitar um passaporte. Dependendo da data de sua viagem pretendida, você pode solicitar um serviço rápido. O Departamento de Estado dos EUA tem uma página da Web que explica essa opção em termos bem claros: link
How can I prove that I am a [US] citizen and leave and come back to the US.
Com exceção de determinadas viagens cobertas pela Iniciativa de Viagem do Hemisfério Ocidental (WHTI), os cidadãos americanos são obrigados por lei a usar um passaporte dos EUA ao entrar e sair do país. Não há, aparentemente, nenhuma penalidade por violar a lei, mas você provavelmente encontrará uma dor de cabeça administrativa se tentar entrar com apenas um certificado de cidadania. Existe também o risco de que o oficial de fronteira possa ser incapaz de provar que o seu certificado é genuíno e, nesse caso, pode ser-lhe recusada a entrada (presume-se que os certificados sejam mais facilmente forjados do que os passaportes).
Mais premente, no entanto, se você estiver tentando viajar de avião, provavelmente não conseguirá embarcar no avião, e ficará preso nesse país até obter um novo passaporte do consulado dos EUA. A única exceção que posso imaginar seria se você também é cidadão canadense, já que os canadenses não precisam de visto para entrar nos EUA.
Outra possibilidade seria se você é cidadão de um país com isenção de visto e, nesse caso, você pode obter autorização da ESTA para viajar com seu outro passaporte. Mas você não deveria fazer isso se você é um cidadão americano (mais, se você estivesse planejando fazer isso, provavelmente não estaria preocupado com o seu certificado de cidadania).
A WHTI aplica-se apenas a viagens terrestres e marítimas. Se a sua viagem for por terra ou por mar, você pode viajar sem passaporte, mas há outros requisitos de identificação para os quais um certificado de cidadania não é suficiente. Os documentos que você pode usar são normalmente cartões de identificação seguros, incluindo o "cartão de passaporte" dos EUA, as chamadas carteiras de habilitação "aprimoradas" e cartões de programa de viajante seguros, como o NEXUS. A lista completa pode ser encontrada aqui: link .
Eu pensei que havia uma lista de países para os quais a ITHO se aplicava, e que seria necessário um passaporte se alguém chegasse por mar de, por exemplo, Europa ou Ásia, mas eu não vejo essa informação no Site do CBP: link .
Para obter seu passaporte, você provavelmente precisará apresentar seu certificado de cidadania, embora um certificado de naturalização também funcione, então você provavelmente deve trabalhar para substituí-lo o mais rápido possível.