As someone that uses remote desktop very frequently, it gets annoying when random issues arise such as the initial connection taking 30+ seconds to finish. Staring at a 'Welcome' spinner for that long, with no reason or merit as to why, gets old fast. My issue was somewhat unique compared to the various similar topics found via Google for this as the server I connect to for one of the things I work on uses a full-on domain controller and Active Directory setup.
When this type of configuration is enabled, your local system has to have network level authentication enabled.
The general fix for the slowness is to set, in the default RDP config, the following option:
In the setup I am discussing here, this is not a valid fix as this disables the NLA features. Attempting to connect to the remote server would then prompt an error stating that NLA is not available and it cannot connect. Interestingly enough though, if you force this feature to enabled, it fixes the slowness issue. So in the default remote desktop configuration, I placed at the bottom:
And the slow connection is fixed.
If you do not need to use NLA at all in your situation, the first code block should be enough to fix the problem for you.
The default remote desktop config file can be found inside of your Documents folder on Windows 8.1+. It is named Default.rdp, which is considered a system file and is hidden by default. So be sure to adjust the folder permissions to view the hidden file. Edit with any standard editor, ie. Notepad++ and you should be good to go.