I don't even think that rebase would get slower as the repo grows. It would only depend on how many commits are being rebased (and the contents of those commits).