You will find that the time taken to clean a track depends on the amount of noise to be removed and the original sounds that are in the track. The program has to work out which is noise and which is audio. If you have a program that shows a graphic map of the sound, you can see that it can be quite a job to sort out.
I have the Steinberg cleaner but have not yet had the opportunity to try it out, but I would expect it to take a while (Especially with some old 45's that I have that have been left collecting dust after being played on a turntable originally intended for 78RPM disks). Just start it off and leave it to do it's job while you watch TV or something.