Msrel_commands table has 20M rows
I've encountered this issue more times than I can count. For some reason, maybe it's an execution plan difference, if you run it manually and also narrow it down it will complete faster than the job. Figure out the max date in there and then do the cleanup manually:

EXEC dbo.sp_MSdistribution_cleanup @min_distretention = 78, @max_distretention = 80
EXEC dbo.sp_MSdistribution_cleanup @min_distretention = 76, @max_distretention = 78
EXEC dbo.sp_MSdistribution_cleanup @min_distretention = 74, @max_distretention = 76
EXEC dbo.sp_MSdistribution_cleanup @min_distretention = 72, @max_distretention = 74


I know this sounds ridiculous, but it is a solution that many of us have had to resort to (I had to google for a solution a few years ago and saw many people needing to do this. One such article). This is one of the reasons why I was so excited to move away from replication when Availability Groups came out.

Make sure you add some monitoring for this condition too that way it doesn't get too far behind when you have to resort to the manual running of sp_MSdistribution_cleanup.