Sounds like you are going to need to change your 7805 to a higher rated chip. I thought that the servos consume somewhere between 400-700mA depending on load. I would check how much current the servo is using to have an idea of how much is the regulator going to have to deliver.
Say you use 1A (that is pretty high for a servo, not sure if it can handle it), then your 7805 will have to waste as heat 7W. A 7805 (in a TO-220)with infinite heat sink is able to waste 20W, check attached graph.
I have driven standard RC servos under 6V and 7.2V. The idea here being that the servo at a higer voltage, will consume less current, and at the same time the regulator has to waste less voltage, therfore reducing the heat.
You may want to also try to use a LM2576HVT-5.0 is a switching regulator. It needs a lot of external part (when compared to the 7805) but it can deliver more.
Ivancho