So, to max it out, let's assume that your reviver empire is willing to support the clones and make sure they have sufficient infrastructure and continuing access to advanced medical technology. This is going to be necessary to some extent regardless since 1000 people probably isn't enough to maintain an advanced economy and tech set on its own and there would be a high probability of one natural disaster wiping them all out, thus wasting the initial investment. "In for a penny, in for a pound" as the saying goes.
Presumably you're cloning 1000 instead of some larger quantity for a reason. Relative expense of cloning vs pre-natal care or something. If you're just going to clone 1000 people and dump them on the planet with some blankets and basic hand tools then this going to take a very long time. And if cloning is cheap, then just make a million clones and be done with it.
Back to the scenario as-presented: Split your first batch of 1000 clones with 750 females and 250 males. Note that in the early years you'll want to mix-and-match the genetics pretty widely to reduce inbreeding problems. You can phase that out as the population grows. Or not. Depends on what kind of culture these people will have, and that's an entirely different discussion.
Best estimates I can find suggest that human females who focus on procreation can get to 15 children with reasonable practicality. Obviously genetic predispositions are a factor, but even the average stone-age female had 8-10, and that's without all the benefits of modern medicine, let alone the medicine of a society capable of mass cloning programs. You'll want to offer cultural and/or financial incentives sufficient to keep the vast majority of people focused on making more people for a while. Small populations are vulnerable to disaster, and the more quickly you get their numbers up, the less you'll spend on infrastructure support in the long-run since they can take over doing it themselves.
The record for number of children is 69, which is kind of an outlier and required an unusual proportion of twins and triplets. The theoretical limit is about 40 pregnancies over the typical lifespan. Very few humans approach that, but if your medical technology is as advanced as one would hope given the cloning thing then you could possibly make it feasible. Or a lower number of pregnancies and use your advanced technology to increase the rate of multiple births. What approach to take depends heavily on the specifics of the "humanlike" physiology we're discussing. For example, if they're marsupials then you could massively increase the birth rate just with artificial milk supply. If they're oviparous then artificial incubation so as to avoid the pause in egg production during the brooding process could easily triple your rate.
So... If you push it to the maximum of 40 in every generation with your advanced medical technology... And keep losses limited as close to entirely among the males as possible...
The 750 females you start with can produce 30,000 new people in the first generation.
The roughly 15,000 of them that are female will bump you up around 600,000 in the second generation.
And the 300,000 females you get from that will put you to 15 million by generation 3.
A generation among humans being roughly 20 years, you're definitely looking at something less than a century, even if we factor in that the birth rate tends to favor males by about 3%, and possibility of accidents.
Cut it down to 20 children each and you hit 15 million in generation 4.
And if you get "lazy" and make it an average of 10 each then it'll be just a bit over 5 generations to get to your original 5 million target. With 15 looking to be the generally accepted maximum practical children per female an average of 10 isn't terribly unreasonable with outside support and strong motivation, and is on a par with our pre-industrial ancestors. That puts your recovery time at about a century. Note that the primary reason for the slow population growth in that era for us was high infant mortality and a high starvation rate. Take those away with a kick-start of advanced medicine and advanced agriculture and the post-industrial population boom can get going right away.
This, of course, assumes that your advanced medical technology and/or genetic engineering really do let you keep deaths from accident and disease to an absolute minimum. And that you have some way to feed everybody. If not, then your growth rate will be more constrained. Although you can mitigate this somewhat by inculcating a culture that will sacrifice males first and prioritize feeding and protecting females and children.
Additionally, if you have good genetic engineering, you could shorten the time further by tweaking the birth rates to favor females. Normal human birthrates favor males slightly (which is then offset by males having a substantially higher mortality rate). Number of females is the hardest limiting factor to overcome with technology, and evolutionary factors tend to push the ratio close to 50/50 even though 80/20 would yield much faster population growth.
Edit: I don't mind downvotes, but do please give some feedback about why... Otherwise I don't know if you're complaining about a math error or the formatting style...