I tried 49 products where there was a mix of Products, Virtual Products, Products with Attributes etc.

No page took longer than 4-5 seconds in the checkout ... The slowest page was the shopping cart itself ... went from 0.4 seconds to 4 - 8 seconds with everything loaded into it and all sideboxes on etc.

I would check to see what your server speeds are like just in navigating around to ensure that your php and MySQL settings are optimized well by your hosting company ...

I would also look at the indexes on your database to ensure that they are all optimized for your site ...