How often should encryption keys be backed up?
Should this be done on the same schedule as the encrypted content/configuration? That seems excessive, as the keys do not change as often.
Perhaps only once, every time the key changes? That sounds dangerous... and I'm not sure it won't leak some cryptoinformation.
Backup is about avoiding loss of data; it is a trade-off between frequency of backups (more backups mean more work and more storage) and tolerance on loss of the most recent data. When you backup your data daily, you implicitly tolerate losing one day's worth of work. Correspondingly, there is no need to backup again data which has not changed -- as long as the previous backup is still good.
When doing regular backups, we actually combine two operations:
Magnetic tapes are often said to be good for ten years or so. Modern paper lasts for a century. Old paper (when they were making it with cotton instead of wood) lasts longer, maybe a millenium (we don't really know yet). Engraved slabs of hard stone, or non-oxidable metal like gold, are best.
There two operations are distinct, and need not be necessarily combined. You want to make new copies regularly, to make sure that the stored backup is still readable; but you do not want to make too many copies of your encryption keys because encryption keys are, by definition, extremely sensitive, and multiple copies are, also by definition, at odds with confidentiality.
Since we are talking about encryption, we can use it to make the problem of backups more manageable. Typically, do it like this:
Store your encryption keys and other critical secrets in a container, say a Zip archive (the Zip file format is reasonably well documented, widely supported, and unlikely to be lost -- for long term archival, file format perennity is a serious concern).
Encrypt that file with a symmetric key (the "master key"), there again using a well-documented, open format which, come what may, could be reimplemented from scratch. OpenPGP would be convenient. The master key can be a big fat password if you prefer it that way. Make it so that it has enough entropy to withstand brute force attacks (80 bits are good, 128 bits are supreme).
Backup the encrypted file in as many places as possible. It is encrypted, so it needs not be especially protected. Keep it on some USB keys, write it in every server you have access to, put it on a Web page and let other people copy it and keep it forever.
Store the master key in two or three safe places. The master key is short, making the problem easier to deal with (that's what encryption does: it does not solve confidentiality issues, but it reduces them). For instance, write it down on a piece of paper, and keep that paper in a bank safe. Make sure that the copies are geographically separated, because floods and earthquakes do happen (usual rule of thumb is to enforce at least 300 km between copies).
For extra points, make the master key an asymmetric encryption key (say, RSA with a large enough key size to make you feel safe -- 2048 bits would be enough for me). This allows you to produce new encrypted archives when you have some new encryption keys to save, using only the public key (the public key being public, you can put it everywhere, including your Facebook account).
(I know of a deployed PKI where the root key backup uses the paper-in-a-bank-safe method. Writing is good. We can read written text from more than four thousand years ago. Can you read an 8" floppy from 1973 ?)
There's not nearly enough information here to give a definitive answer. I can, however, leave you with a few things to think about and make a decision on based on your evaluation of risk. The most important thing to remember is that losing your encryption key is equivalent to losing ALL backup sets encrypted with that key.
In light of that, what are your recovery objectives? How much loss can you afford? What is the reliability of the media? My general answer would be that you need to back up your keys frequently enough to guarantee a successful recovery from your storage media. In light of this, I would seriously give thought to restoring and testing keys after every backup, regardless of the schedule you choose. If the risk of key loss is substantial, you may even want to look at hardware security modules for escrowing your keys.
I'm a little unclear as to what your worry about information leakage is. Cryptography assumes that the attacker knows you've chosen some key and that your information is encrypted as part of its threat model for encryption.
