It wont take forever, but it will take some time, there’s no avoiding that.
The 120 limit is enough to get through 12k follows/min. If you actually have 10k channels using your app and you can show sufficient need then you could request a rate limit increase and significantly increase that limit which would allow you to build your cache faster.
You could also prioritise your requests, for example, if one of the channels that has authorised your bot is live you could get the follow status of the users in those channels first, and only then move on to building a full cache for offline channels.
Webhooks, and monitoring follower count, are ways to help maintain the caches accuracy, but there is simply no avoiding that it will take time to build the initial cache.