I believe this is due to the number and size of file paths more than numbers of versions.
Most likely (and this is just a guess) it’s getting longer simply due to having more file paths with each run as new files are added. In theory you should eventually reach a balance point where file additions and historical cleanup deletions even out at which point performance should also level out.
Yes, it’s a known issue and yes, things are being done to address it. The problem is that it’s a MAJOR rewrite to implement a more efficient file path handling method, so it takes time to get it all in place and tested.
More recently (as in 2 hours ago) a suggestion was made that might be relatively easily implemented and could improve RESTORE times (but likely have little to no effect on other performance issues):