Infelizmente vou dizer, independente da solução o que você deseja não é possível, em um ponto ou outro o mesmo pode ser quebrado, simulado ou emulado.
Chave assimétrica ou simétrica não muda isso.
Todas essas técnicas apenas vão dificultar, mas nunca inibir as ações de alguém com conhecimento e interesse.
Nestes casos você deve trabalhar com o tipo de segurança que vale a pena. Não coloque algo muito complexo pois precisa dar manutenção, nem coloque algo sofisticado de mais, pois talvez uma simples key nunca será vista. Tudo depende do tipo de aplicação e do interesse dos que tem conhecimento.
Dando apenas uma linha para se guiar, veja como obscurecer seu código. Usar mescla de Java com C também ajuda.
Obscurecer também pode ser usado a nível de API, mas nestes casos você usa algo como o swagger para definir a API, e depois alguma outra solução dependendo da linguagem para embaralhar as requisições.
Use SSL no endpoint dificulta a quebra, se usada junto como GRPC já aumenta o nível de complexidade com ganhos de performance mas com o aumento do gasto na infraestrutura.
Uma solução é usar uma chave em cada versão do APK. Sempre que uma nova versão sair você desabilita o acesso de 1 ou 2 versões anteriores, se juntar isso com o GRPC, e talvez com a geração de 'login' por aplicação instalada, cada uma mantendo uma chave registrada, ou mesmo um próprio login onde você retorne uma chave para ser usada (assimétrica) onde você pode cancelar seletivamente as que desejar.
user-agent
da requisição, mas isso é manipulável e qualquer garotinho de 12 anos desocupado sabe fazer isso. Não perca o sono por causa desse requisito de não poder acessar a API a partir de navegador, pois é uma luta perdida ;)