La batería puede ser correcta pero no esperes usar a Arduino para alimentar todo usando su salida 5V. Ese es un error común.
En cambio, si puedes alimentar arduino con los 12V de la batería por un lado y ver como alimentas el Servo.
No has dicho que servo es como para sugerirte tal o cual conexión.
A la espera de ese dato espero tu próxima consulta.