Increasing need for secure voice communication is leading to new ideas for securing voice transmission. This work relates to a relatively new concept of sending encrypted speech as pseudo-speech in audio domain over existing civilian voice communication infrastructure, like 2G-4G networks and VoIP. Such a setting is more universal compared to military “Crypto Phones” and can be opened for public evaluation. Nevertheless, secure communication requires a prior exchange of cryptographic keys over voice channels, without reliance on any Public Key Infrastructure (PKI). This work presents the first formally verified and authenticated key exchange (AKE) over voice channels for secure military-grade voice communications. It describes the operational principles of the novel communication system and enlists its security requirements. The voice channel characteristics in the context of AKE protocol execution is thoroughly explained, with a strong emphasis on differences to classical store-and- forward data channels. Namely a robust protocol has been designed specifically for voice channels with double authentication based on signatures and Short Authentication Strings (SAS). The protocol is detailed and analyzed in terms of fundamental security properties and successfuly verified in a symbolic model using Tamarin Prover.