Underwater acoustic communications have found applications in many fields with great developments. Thus, the demand for security of such communications is rapidly growing. Two parties in the communication, after authentication, generally use a secure symmetric key to encrypt all the data they transmit. Thus, an efficient key generation algorithm is in urgent need to guarding the privacy of the communication data. This paper presents a novel key generation system which is easy to be implemented, efficient in computation and communication, and robust to the spatio-temporal variable ocean environments. Un- like those conventional solutions, by exploiting reciprocity, deep fades, randomness extractor and robust secure fuzzy information reconciliators, which is first introduced by us in this paper, channel characteristics are used to generate the key in our solution.