A method and wireless device for updating at least one cryptographic security key (116) associated with a wireless device (104) and an authentication module (108). An over-the-air programming message comprising security key update information is received (804) from an information processing system (118). The security key update information is processed (808). At least one new security key is extracted from the security key update information in response to the processing (806). At least one existing security key (116) is updated with the at least one new security key (124) that has been extracted.