Oh yes, a fair warning to those who are still using an iPhone 5 / DON'T UPDATE TO IOS 9!!! I was stupid enough to do so and it has made my iPhone as slow as thick mud through a funnel.

Has it been at least 24 hours since you upgraded, and has the device sat in a charger unused during that time?
iOS major upgrades (8 to 9 here) wipe all device cache, and frequently wipe the spotlight DB. The slowness you are seeing right now may be tied to those caches and optimizations needing to be rebuilt. The phone is doing some of this in the background, and can usually complete it overnight when sitting in a charger.
Ok, it turns out this was effectively the problem. Yesterday (even a few hours after the update), when I pressed the home or power button eg, it took the phone 5 seconds or more to respond. Writing text was next to impossible because it took the keyboard 10 seconds to show up and seconds to respond to every single tap.
But now all seems fine, so I guess you were right Tom! (thank God!). I've been updating my phone with every possible update since iOS 6, but this is the first time this was the result, hence my initial reaction. But all seems fine now, it indeed doesn't seem slower than iOS 8.x was.
I retract my initial statement.

It's not all gold that glitters though... My main reason for updating was because iOS 9 finally supported ad blockers. Unfortunately, this only seems to work from iPhones 5s and up.

I've read somewhere this is because the phone needs a 64 bit CPU for this to function properly. Oh well...