It's true that key rotation would mean changing your IP address, but that is something that is fairly routine on the current internet already, though certainly infrequently done by major sites and services.
The primary purpose of the encryption in CJDNS is simply to establish identity and make the completely decentralized addressing system (the key component) possible. Using the keys to do built in transparent end-to-end encryption is an important and valuable feature as well, but ultimately is secondary. If you need the kind of security that requires frequent key rotation, you should really be using an additional encryption and identity verification layer on top, just like with the current internet.
Also, CJDNS uses 512 bit keys, and the nature of how the protocol works means that any address collisions (which would be unavoidable by someone impersonating you) would be obvious and detectable, so for it's intended purpose it should not be necessary to rotate keys very often at all.
Currently the typical solution on Hyperboria is indeed the current internet DNS system, primarily for lack of a widely accepted decentralized alternative.
A truly decentralized alternative to the current DNS system is a difficult problem to solve, and one that people continue to work on. IP addresses are easier because they are interchangeable, it really doesn't matter which one you have as long as you're the only one who has it. Domain names, though, are not at all, in fact that's basically their entire point. The question of who gets which names, issues around fraud and phishing, mass registration and domain squatting... how do you solve those problems without some sort of authority to arbitrate and enforce rules?
The closest alternative to the ideal that I know of right now is probably Namecoin, which works quite well with Hyperboria, but it still involves a number of compromises that not everyone is happy with.
