Next number with k fives
R, 85 84 76 74 bytes, 0.250s on TIO

f=function(n,k,m=nchar(gsub(&quot;[^5]&quot;,&quot;&quot;,n+1))-k)`if`(m&lt;0,f(n+.1^m/50,k),n+1)

Try it online!
-1 byte thanks to Robert S.
-8 bytes thanks to Giuseppe.
The nchar(gsub(...)) part counts the number of 5s.
A simple recursive solution would be to increment by 1 until the answer is found, but this would not meet the time restriction. To meet the time restriction, this function makes use of the fact that if there are p missing 5s, we can increment by 2*10^(p-2) (represented as the golfier .1^m/50, with m=-p).
Note that when p=1, the increment becomes 0.2. This is OK, since after 5 steps we come back to an integer, and none of the decimal numbers encountered in the mean time have an extra 5. If instead we were to increment by 5*10^(p-2) or by 1*10^(p-2), then we would find f(24, 1)=24.5 instead of 25 for example.