How long should it take to charge up a new iPhone
No this is not normal.

An iPhone should not be using so much power overnight that a normal charge source cannot top it off in 4 hours.

The problems could be:


stuck process on the CPU of the phone.
faulty hardware on the iOS side
insufficient charge from the USB


You can rule out the first by connecting the phone to charge and then powering it off. It will charge safely when powered off as the charge circuitry doesn't need the phone to be running.

The second problem might be a used up battery, a prematurely failing battery, damage to the internal charging circuitry.

The third problem could be as simple as the Mac not charging during hibernation (it would charge during sleep at 500mA level) or a bad cable or faulty port power. You can rule that out by charging from a proper wall adapter.