I did a similar thing except I converted the QR codes to unicode-art and saved them in a GPG encrypted file. It's probably not as safe as hardcopies in a safe, but it's more convenient (and it was fun reading QR codes out of a terminal window).

Authy makes me a little nervous (since it's closed source and I can't be sure exactly what they are doing), but at least they claim to encrypt the keys on the phone before they put them on their servers. They state on their site repeatedly that if you forget your encryption password the keys are gone and they can't do anything about it.