There are multiple questions here, and some of them are asked & answered earlier. First, the question about computation taking a long time. There are multiple methods to deal with that, see https://stackoverflow.com/questions/3169371/large-scale-regression-in-r-with-a-sparse-feature-matrix and the paper by Maechler and Bates.
But it might well be that the problem is with modeling, I am not so sure that the usual methods of treating categorical predictor variables really give sufficient guidance when having categorical variables with very many levels, see this site for the tag
[many-categories]. There are certainly many ways one could try, one could be (if this is a good idea for your example I cannot know, you didn't tell us your specific application) a kind of hierarchical categorical variable(s), that is, inspired by the system used in biological classification, see https://en.wikipedia.org/wiki/Taxonomy_(biology). There an individual (plant or animal) is classified first to Domain, then Kingdom, Phylum, Class, Order, Family, Genus and finally Species. So for each level in the classification you could create a factor variable. If your levels, are, say, products sold in a supermarket, you could create a hierarchical classification starting with [foodstuff, kitchenware, other], then foodstuff could be classified as [meat, fish, vegetables, cereals, ...] and so on. Just a possibility.
Orthogonal to the last idea, you could try fused lasso, see Principled way of collapsing categorical variables with many categories which could be seen as a way of collapsing the levels into larger groups, entirely based on the data, not a prior organization of the levels as implied by my proposal of a hierarchical organization of the levels.