Ubuntu 20.04 taking too long to boot up

I have upgraded Ubuntu 19.10 to 20.04 and since then, it is significantly taking a long time (about 2 minutes to boot up). Yet, systemd-analyze shows that it only took 1 minute to boot up:

Startup finished in 22.428s (kernel) + 1min 3.775s (userspace) = 1min 26.203s 
graphical.target reached after 1min 3.627s in userspace

As mentioned in other answers, I ran dmesg and I have found some huge time gaps in between the timestamps. Here is the complete output of dmesg command since it exceeded the character limit.

For your convenience, I should mention that there is a gap between 3 to 21, 37 to 52, 57 to 71 and 71 to 105 seconds. Here are those parts:

[    3.295687]  sdb: sdb1
[    3.298520] sd 4:0:0:1: [sdb] Attached SCSI removable disk
[   21.385823] EXT4-fs (sda3): mounted filesystem with ordered data mode. Opts: (null)
[   22.804433] systemd[1]: Inserted module 'autofs4'
[   37.790817] audit: type=1400 audit(1593936297.560:10): apparmor="STATUS" operation="profile_load" profile="unconfined" name="/usr/lib/cups/backend/cups-pdf" pid=752 comm="apparmor_parser"
[   37.790820] audit: type=1400 audit(1593936297.560:11): apparmor="STATUS" operation="profile_load" profile="unconfined" name="/usr/sbin/cupsd" pid=752 comm="apparmor_parser"
[   52.530237] kauditd_printk_skb: 13 callbacks suppressed
[   52.530240] audit: type=1400 audit(1593936312.300:25): apparmor="DENIED" operation="capable" profile="/usr/sbin/cups-browsed" pid=884 comm="cups-browsed" capability=23  capname="sys_nice"
[   56.453158] Generic FE-GE Realtek PHY r8169-200:00: attached PHY driver [Generic FE-GE Realtek PHY] (mii_bus:phy_addr=r8169-200:00, irq=IGNORE)
[   57.951318] RTL871X: cfg80211_rtw_dump_station(wlx00e0202c7613)
[   57.951319] RTL871X: Station is not found
[   71.956183] PPP BSD Compression module registered
[   71.996804] PPP Deflate Compression module registered
[  105.398067] rfkill: input handler disabled

I have Ubuntu installed in an HDD and its the only OS in the disk. Upon checking my HDD, I didn't find any slowdown and it is working properly. Ubuntu 19.10 used to boot up much faster. After the boot process finishes, Ubuntu runs perfectly fine and the shutdown process is also very fast (about 5 seconds). Is there any way to fix this slow boot issue without reinstalling everything?

EDIT:
This is the output of systemd-analyze blame command:

35.198s plymouth-quit-wait.service                           
16.844s udisks2.service                                      
15.443s networkd-dispatcher.service                          
15.292s accounts-daemon.service                              
15.175s systemd-journal-flush.service                        
12.570s phpsessionclean.service                              
10.225s apport-autoreport.service                            
 8.504s ModemManager.service                                 
 7.997s plymouth-read-write.service                          
 7.200s NetworkManager.service                               
 6.908s dev-sda3.device                                      
 6.709s polkit.service                                       
 6.434s avahi-daemon.service                                 
 5.979s thermald.service                                     
 5.978s systemd-logind.service                               
 5.973s wpa_supplicant.service                               
 3.870s apparmor.service                                     
 3.841s grub-common.service                                  
 3.680s apport.service                                       
 3.325s ssh.service                                          
 3.157s udhcpd.service                                       
 3.106s gdm.service                                          
 3.029s gpu-manager.service                                  
 3.021s ufw.service                                          
 2.924s rsyslog.service                                      
 2.148s systemd-modules-load.service                         
 1.969s [email protected]                                    
 1.867s systemd-udevd.service                                
 1.732s grub-initrd-fallback.service                         
 1.667s systemd-fsck@dev-disk-by\x2duuid-E766\x2dD5EE.service
 1.582s lm-sensors.service                                   
 1.203s plymouth-start.service                               
  980ms systemd-tmpfiles-setup-dev.service                   
  976ms colord.service                                       
  944ms kerneloops.service                                   
  844ms systemd-resolved.service                             
  796ms systemd-udev-trigger.service                         
  763ms systemd-rfkill.service                               
  762ms keyboard-setup.service                               
  761ms systemd-sysusers.service                             
  712ms systemd-tmpfiles-setup.service                       
  676ms [email protected]                                 
  675ms systemd-journald.service                             
  607ms upower.service                                       
  571ms systemd-sysctl.service                               
  549ms swapfile.swap                                        
  528ms binfmt-support.service                               
  509ms systemd-random-seed.service                          
  497ms alsa-restore.service                                 
  458ms hddtemp.service                                      
  420ms e2scrub_reap.service                                 
  384ms boot-efi.mount                                       
  347ms pppd-dns.service                                     
  342ms systemd-timesyncd.service                            
  264ms openvpn.service                                      
  221ms systemd-user-sessions.service                        
  177ms systemd-remount-fs.service                           
  144ms setvtrgb.service                                     
  120ms dev-hugepages.mount                                  
  119ms dev-mqueue.mount                                     
  118ms sys-kernel-debug.mount                               
  118ms sys-kernel-tracing.mount                             
  116ms proc-sys-fs-binfmt_misc.mount                        
  115ms kmod-static-nodes.service                            
  107ms console-setup.service                                
   63ms systemd-update-utmp.service                          
   55ms rtkit-daemon.service                                 
   20ms [email protected]                        
    9ms systemd-update-utmp-runlevel.service                 
    2ms sys-fs-fuse-connections.mount                        
    2ms sys-kernel-config.mount

This is the output of systemd-analyze critical-chain command:

The time when unit became active or started is printed after the "@" character.
The time the unit took to start is printed after the "+" character.

graphical.target @1min 4.202s
└─multi-user.target @1min 4.202s
  └─networkd-dispatcher.service @21.522s +15.443s
    └─basic.target @21.044s
      └─sockets.target @21.044s
        └─uuidd.socket @21.044s
          └─sysinit.target @20.882s
            └─systemd-timesyncd.service @19.201s +342ms
              └─systemd-tmpfiles-setup.service @18.486s +712ms
                └─systemd-journal-flush.service @3.310s +15.175s
                  └─systemd-journald.service @2.633s +675ms
                    └─systemd-journald.socket @2.629s
                      └─-.mount @2.311s
                        └─system.slice @2.311s
                          └─-.slice @2.311s

These are the contents from /var/log/boot.log file for the recent boot:

------------ Sun Jul 05 15:56:18 IST 2020 ------------
[  OK  ] Listening on Load/Save RF Kill Switch Status /dev/rfkill Watch.
[  OK  ] Started Show Plymouth Boot Screen.
[  OK  ] Started Forward Password Requests to Plymouth Directory Watch.
[  OK  ] Reached target Local Encrypted Volumes.
         Starting Load/Save RF Kill Switch Status...
[**    ] (1 of 3) A start job is running for Load/Save RF Kill Switch Status (48[  OK  ] Found device WDC_WD10EZEX-22MFCA0 EFI\x20System\x20Partition.
         Starting File System Check on /dev/disk/by-uuid/E766-D5EE...
[  OK  ] Started File System Check Daemon to report status.
[  OK  ] Started Load/Save RF Kill Switch Status.
[  OK  ] Finished File System Check on /dev/disk/by-uuid/E766-D5EE.
         Mounting /boot/efi...
[  OK  ] Mounted /boot/efi.
[  OK  ] Reached target Local File Systems.
         Starting Load AppArmor profiles...
         Starting Enable support for additional executable binary formats...
         Starting Set console font and keymap...
         Starting Tell Plymouth To Write Out Runtime Data...
[  OK  ] Finished Set console font and keymap.
         Mounting Arbitrary Executable File Formats File System...
[  OK  ] Mounted Arbitrary Executable File Formats File System.
[  OK  ] Finished Enable support for additional executable binary formats.
[  OK  ] Finished Load AppArmor profiles.
[  OK  ] Finished Flush Journal to Persistent Storage.
         Starting Create Volatile Files and Directories...
[  OK  ] Finished Create Volatile Files and Directories.
         Starting Network Name Resolution...
         Starting Network Time Synchronization...
         Starting Update UTMP about System Boot/Shutdown...
[  OK  ] Finished Update UTMP about System Boot/Shutdown.
[  OK  ] Started Network Time Synchronization.
[  OK  ] Reached target System Time Set.
[  OK  ] Reached target System Time Synchronized.
[  OK  ] Started Network Name Resolution.
[  OK  ] Reached target Host and Network Name Lookups.
[  OK  ] Finished Tell Plymouth To Write Out Runtime Data.
[  OK  ] Reached target System Initialization.
[  OK  ] Started ACPI Events Check.
[  OK  ] Started Process error reports when automatic reporting is enabled (file watch).
[  OK  ] Started CUPS Scheduler.
[  OK  ] Started Trigger anacron every hour.
[  OK  ] Started Periodic ext4 Online Metadata Check for All Filesystems.
[  OK  ] Started Discard unused blocks once a week.
[  OK  ] Started Refresh fwupd metadata regularly.
[  OK  ] Started Daily rotation of log files.
[  OK  ] Started Daily man-db regeneration.
[  OK  ] Started Message of the Day.
[  OK  ] Started Clean PHP session files every 30 mins.
[  OK  ] Started Daily Cleanup of Temporary Directories.
[  OK  ] Reached target Paths.
[  OK  ] Reached target Timers.
[  OK  ] Listening on ACPID Listen Socket.
[  OK  ] Listening on Avahi mDNS/DNS-SD Stack Activation Socket.
[  OK  ] Listening on CUPS Scheduler.
[  OK  ] Listening on D-Bus System Message Bus Socket.
[  OK  ] Listening on Erlang Port Mapper Daemon Activation Socket.
[  OK  ] Listening on UUID daemon activation socket.
[  OK  ] Reached target Sockets.
[  OK  ] Reached target Basic System.
         Starting Accounts Service...
[  OK  ] Started ACPI event daemon.
         Starting Save/Restore Sound Card State...
[  OK  ] Started Run anacron jobs.
         Starting LSB: automatic crash report generation...
         Starting Avahi mDNS/DNS-SD Stack...
[  OK  ] Started Regular background program processing daemon.
[  OK  ] Started CUPS Scheduler.
[  OK  ] Started D-Bus System Message Bus.
         Starting Network Manager...
[  OK  ] Started Save initial kernel messages after boot.
         Starting Remove Stale Online ext4 Metadata Check Snapshots...
[  OK  ] Reached target Login Prompts.
         Starting Detect the available GPUs and deal with any system changes...
         Starting LSB: Record successful boot for GRUB...
         Starting GRUB failed boot detection...
[  OK  ] Started irqbalance daemon.
         Starting Initialize hardware monitoring sensors...
         Starting Dispatcher daemon for systemd-networkd...
[  OK  ] Started Set the CPU Frequency Scaling governor.
         Starting Authorization Manager...
         Starting Restore /etc/resolv.conf if the system crashed before the ppp link was shut down...
         Starting System Logging Service...
         Starting Login Service...
         Starting Thermal Daemon Service...
         Starting LSB: Start busybox udhcpd at boot time...
         Starting Disk Manager...
         Starting WPA supplicant...
[  OK  ] Finished Remove Stale Online ext4 Metadata Check Snapshots.
         Starting Clean php session files...
[  OK  ] Finished Save/Restore Sound Card State.
[  OK  ] Reached target Sound Card.
[  OK  ] Finished Restore /etc/resolv.conf if the system crashed before the ppp link was shut down.
[  OK  ] Finished GRUB failed boot detection.
[  OK  ] Finished Initialize hardware monitoring sensors.
[  OK  ] Finished Detect the available GPUs and deal with any system changes.
[  OK  ] Started System Logging Service.
[  OK  ] Started LSB: Start busybox udhcpd at boot time.
[  OK  ] Started LSB: automatic crash report generation.
[  OK  ] Started LSB: Record successful boot for GRUB.

It was Gnome desktop environment (GDM) which was taking so much time to boot up. I have replaced GDM with lightDM and now my system takes less than 30 seconds to boot up!

Regarding the kernel part, I have noticed that whenever the system shuts down abnormally, such as a power failure, the kernel takes more time to boot up the next time. If the system is shut down normally, the kernel takes less than 10 seconds to boot up.

Here is the current output of systemd-analyze:

Startup finished in 9.704s (kernel) + 28.376s (userspace) = 38.081s 
graphical.target reached after 26.279s in userspace