Another consideration may be the system memory. Sometime if your memory is starting to go, boot times can increase and overall responsiveness of the computer will decrease.
If you can, try some alternate memory or at least swap out the modules and test them.