Your framerate should be as low as looks good, but I think you're in a tough situation if all of your sprites are moving constantly. You should try your absolute hardest to keep a consistent framerate; a low, consistent framerate is better than a high but randomly stuttering framerate. Then turn it down until it doesn't look good.
Consider matching the framerate of movies on the big screen: they are only 24 FPS. But again, they are precisely consistent, which is why people are okay with just 24 FPS.
Alternatively, if your sprites have an animation sequence and that has a FPS value, try matching that or a multiple of it. For example if they animate at 5 frames per second, then maybe try 25 or 30 frames per second so that the sprite animations can be precisely timed and make the game appear more smooth and consistent than it really is.
I think the best option in this case is to try out some framerates and find a good default, and then put a setting in your options menu for the user to be able to turn it up or down according to the user's desired battery life.