Haskell, 170 bytes

f 0='A'
f n|x<-f$div n 5=(x:drop(sum[4|l<-['A'..'Y'],l<x])"DDAXISONAMELINGOAGLEOSSAECKOORSENDRIAMBUOALAEMUROUSEYALATTERRAWNUAILOBINQUIDIGERRIALIXENHALEERUSAPOK")!!mod n 5

Try it online!

This exceeds TIO's output capacity nearly instantly, so I think this is safe on timing. My quick analysis tells me the algorithm should be \$O(\mathrm{log}(\mathrm{log}(n)))\$. That is if you input a number of length \$n\$ bits it should take about the \$\mathrm{log}(\mathrm{log}(n))\$ time to find the answer.

I'm not the best at golfing data encoding so I think that is where I am losing the most bytes.

This gets a lot easier to read if we just say we have a function u which gives the word for a letter. Then it is:

f 0='A'
f n=u(f$div n 5)!!mod n 5