Establishing OpenVPN connection only works on the 2nd try

I'm running a debian-server with OpenVPN and I'm trying to establish a connection to it over the internet (windows client). However I've noticed that it always takes a long time, since it seems to hit the timeout.

I always get to this part:

MANAGEMENT: >STATE:1561445206,WAIT

at the end of the timeout, I get this:

TLS Error: TLS key negotiation failed to occur within 60 seconds (check your network connectivity)
TLS Error: TLS handshake failed

HOWEVER, then my client tries to connect again (after 5 seconds) and it immediately establishes the connection.

SIGUSR1[soft,tls-error] received, process restarting
MANAGEMENT: >STATE:1561445266,RECONNECTING,tls-error,,,,,
Restart pause, 5 second(s)
TCP/UDP: Preserving recently used remote address: [AF_INET]x.x.x.x:x
Socket Buffers: R=[65536->65536] S=[65536->65536]
UDP link local: (not bound)
UDP link remote: [AF_INET]x.x.x.x:x
MANAGEMENT: >STATE:1561445271,WAIT,,,,,,
MANAGEMENT: >STATE:1561445271,AUTH,,,,,,

90% of the time it works like this where it only connects on the second try - sometimes it also (seemingly at random) connects on the first try