It is make sense that PostgreSQL make too long to start, About 20 minutes. I'm using PostgreSQL 12 intalling on Ubuntu Server 18.04 and my database is about 25 GO of data.
Every time? How are you shutting down the server?
Additionally, you will want to examine, and probably relay, the contents of the log file during these shutdown/startup periods.