I would recommend using twitter / snowflake solution for that purpose. I had very similar requirement and that approach worked perfectly for me.
I used Flake ID Generator. It is .net implementation based on twitter / snowflake.
The generator can be independently deployed to different Azure instances (or work as a independent service) - I was generating ids independently on each Azure service instance. Generated 64-bit ids are directly sortable and always unique (even if come from the different instances at the same time). You also have access to its source code so you can also add customizations if needed.
I hope that will help.