Firstly, apologies for the delay in responding here and any inconvenience this issue may have caused.
Can you please check if port 22 is accessible on Public IP using this link. If this is open, then port is open and good for the ssh connection. Incase if the port shows as closed, then check rules on all the NSG's impacting the subnet of the VM.
If the VM is accessed via a Bastion, the it could be an unstable network connection to bastion host.
VM Taking more than 20 mins to start, this depends on the multiple reasons.
What applications are running on this VM? It could be high usage of the CPU & Memory causing this.
It could also be with the image the VM was launched. Was this a custom image or one from marketplace.
Try to upgrade the VM size, Stop the VM and change the SKU type with better CPU and RAM and Start the VM again. If this fixes the startup time, then it is mostly due to the apps load. If you have multiple apps running, try and split them to balance the load.
Try to redeploy the VM and ensure NSG on the subnet has the port 22 open.
Try to deploy VM in another subnet and check if that helps.
Hope this helps.
Please 'Accept as answer' if the provided information is helpful, so that it can help others in the community looking for help on similar topics.