Login lasts too long

The game tries to login, but never ends. Whenever I try to open the game, my account does not load until 10 or 20 minutes have passed. I cannot play in my own worlds, open the Marketplace, or even open the settings until the login succeeds. This makes the game unplayable.

Steps to reproduce:
Open the game / Open the game and press the Log In button

Expected Results:
The Microsoft account loads in 5-7 seconds

Observed Results:
The Microsoft account never loads / lasts too long (at least 20 minutes) to load.