Yes, you are right. Never use the Arduinos 5V-Regulator to supply servos.
When I build stuff like your project, I often use 2-Cell-Lipos (2S 800 mAh) in combination with small 5V UBECs. I connect the 5V output from the UBEC directly to 5V Pin on Arduino and Servo.
But keep in mind, LiPos require a special charger with balancer to charge them safely.
