Public key: that's the easy part, it can be almost anywhere (known URL, some type of file store like S3/GCS/..., even source control). The only concern is to make sure it is not modified, but it can be read by anyone.
Private key: this is where it gets tricky.
The private key should be as safe as possible with access as limited as possible.
If someone reads your private key, they can pretend to be your service. You are correct that it must not be in source control.
You'll want to make sure the private key is always encrypted. The issue now becomes how to give your service the passphrase to decode the key. The encrypted file itself can be in a cloud storage system (S3, GCS, etc..). Some access controls on the encrypted file is still a good idea.
Some ways to access the passphrase (definitely not exhaustive). Each has pros and cons. Which to use depends a lot on your environment and balancing automation vs security.
environment variable: many deployment systems allow you to specify environment variables in a way that is not easily read by anyone but administrators of the system. This might not be safe depending on the production environment and who has access to the VM/orchestration system.
manage your own: use your own infrastructure to distribute secrets. Things like keywhiz and Vault can be very powerful, but these are not simple systems to deploy and manage.
cloud KMS: make use of the cloud-specific Key Management System (eg: Google/AWS KMS, Azure Vault, etc...). They usually cannot store a file, but they can store a key with which to encrypt a file. The permissions on key usage should be very restricted, this can usually be done per role account and assigned only to your service.
human interaction required: require that someone manually login to the system and decrypt the private key for use by the backend. The obvious downside is that there is no automation there, if your VM goes down it cannot be automatically restarted.