Is it true that, for all sufficiently large $n$, there exists some $k$ such that $$p(n+k)>k^2+1,$$ where $p(m)$ denotes the least prime factor of $m$?

Can one prove this is false if we replace $k^2+1$ by $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$, for all $\epsilon>0$, where $C_\epsilon>0$ is some constant?