iPhone 5S slow installation

I am just installing my new iPhone 5S. I selected it to restore an iCloud copy (from my 4S), but the installation is taking forever, is it normal?
It reboots to the apple-logo with the progressbar, but the progressbar just freeze at like 20% (well atleast for 2h) then i restarted the phone. The progressbar restarts it seems but it still is incredible slow.
Hints anyone?

I hold the start and start/sleep wakebutton and then it powers off and I power it on again.