It's difficult to determine the exact timeframe for Google to remove old permalinks and index new URLs. In general, Google may take a few weeks to a few months to fully crawl and index your website. Your website's page changes can take effect at different speeds depending on various factors. The size of your website, the number of modified pages, and the frequency of Google crawling your site are all factors to consider.
You may speed up the process by requesting a re-crawl of your website using Google Search Console. This will cause Google to reindex your website's pages and update its search results faster.