Have you tried restoring the phone yet? I do this about once every other month to keep the "Other" directory from chewing through my storage space (I use iTunes Match, which can leave garbage data behind that only a device restore will delete), and I think it helps keep the device running reliably. My typical battery life on my 5s is 5-6 hours, and this has stayed fairly consistent through different iOS versions.
Another suggestion would be to change the background app refresh and location services settings. Apps that aggressively poll the GPS will drain the battery very quickly. Just from a two hour bike ride, the GPS app I use to track my route will drain the battery by 30 percentage points. That's with the phone on standby the entire time.
The 5c did not have a battery recall, and the recall for the 5 only affected early production units manufactured during a specific period. That doesn't preclude your phone from having a bad battery.