Years ago i had faced a similar issue where the check db took a lot of time to complete.The issue was later found to be with the disk system and we had to move the database to another server.

However this was also accompanied by a reduction in performance of the database.Is your applcation running slowly too?You could get the disk system checked out.