New agent package is your only choice if all your ePO servers are running different security keys. If the keys don't match then the agents will fail the authentication process with the DNS method.
One option to try is to 'register' the other ePO servers on the primary ePO server and tranfers all the systems from one to the other (pages 95 and 148 of the 4.6 ePO product guide) but this only works with certain ePO versions.
Thankyou for the suggestion. I forget to mention the ePO version details. 3 ePO consoles are running with 3.6 and 2 are running with 4.0. The registry option will work for 3.6 version? Please suggest.
Sadly i think the registered server option only works with 4.5 and 4.6 servers (but don't quote me, someone else more knowledgable might be able to confirm this).
Personally in this situation i would take the opportunity to install a brand new ePO 4.6 server and redeploy new agents to all systems. But that all depends on numbers of clients, licensing, manpower etc .
I have found this post on a 3.6 to 4.5 upgrade path
If you could upgrade all servers to a single version (say 4.5) then you'll be able to go down the registered server path.
i would say just pick your one server to upgrade to 4.5, then deploy a new frame package to all the systems. Sucks but I think in this case it would be your best option.