Go to appleid.apple.com. Under "Password and Security", you can generate a new recovery key. I think the old one should also still work, but I'm not sure, so it's probably better to get a new one.
BTW, the recovery keys will be phased out as Apple updates people to the new 2-factor authentication over the next few months.