you need to go to recovery (with phone off, power on+hold down volume), it say nand backup/restore. Everything will be backed up. I never had my keys deleted and i must have flashed like a billion times. But as long as you have the nand backup you should be good.
http://forum.xda-developers.com/showthread.php?t=936945