The quickest and safest method of replacing the Frontend agent certificates is to uninstall and then reinstall the frontend servers again.
However, this installation reinstallation will be done slighly differently, as since your Frontend Server is already registered to the backend, you want to avoid having to re-attach all the applications/consoles to the Frontend server.
...
You also need to make sure the agent names match exactly what you already have listed under Authentication>Agents on your Administration Console. (refer back to the start of this wiki.You would have noted the names earlier, as mentioned above)
New Frontend Agent Certificates will be installed during the process.
...