Each phone shall have a button (hard or soft) which can be pressed by the caller at any time. Pressing it will cause a new TDES key to be generated and exchanged. [Should it generate a new n and g for D-H, or just create a new x and demand a new Y?] Paranoid users can press this button every few seconds if they wish. (In my humble opinion, even a single-DES phone is quite secure if it has this feature.)
It might be possible to compute the DH in the background while the conversation is going on, but if the computer is also compressing, uncompressing, encrypting and decrypting at the same time, that's not going to be easy.
Another thing to remember is that out of the DH you're going to get somewhere in the neighborhood of 1000 - 2000 bits of secret. Assuming triple DES you only eat up 3*56 = 168 (you may actually use 3*64 = 192 just to keep life simple) of these bits. You can rekey 5-10 times without having to re-exponentiate. Eric Blossom