Rule 9 in Appendix G of the TeXbook:
9. If the current item is an Over atom (from \overline), set box x to the nucleus in style C'. Then replace the nucleus by a vbox containing kern θ, hrule of height θ, kern 3θ, and box x, from top to bottom, where θ = ξ8 is the default rule thickness. (This puts a rule over the nucleus, with 3θ clearance, and with θ units of extra white space assumed to be present above the rule.) Continue with Rule 16.
The rule thickness is stored in \fontdimen22\textfont3 (the large symbols font; \textfont will be \scriptfont in subscripts or superscripts) and it's 0.4pt for Computer Modern.
In NewTX it's 0.56pt, so not only the rule is (a bit) thicker, but also the clearance is wider, by 0.48pt. Not so large an amount, but noticeable in context.
To the contrary, the \bar accent is placed according to rule 12 (a lot more complicated), which results in a much smaller clearance.
There's no way to reduce the clearance for \overline, as it's built in TeX (possibly LuaTeX can overcome this), unless the \fontdimen is changed when the font is first loaded in memory.
Just by way of example
\documentclass{article}
\usepackage{newtx}
\sbox0{$\fontdimen8\textfont3=0.4pt$}
\begin{document}
$\overline{k}$ $\bar{k}$
\the\fontdimen8\textfont3
\end{document}

We could reimplement \overline using the same rule 9, but with a different clearance (the optional argument is the amount of clearance as a multiple of the rule thickness). If you want to follow this path, you can remove the \NewCommandCopy line that's just for the final comparison.
\documentclass{article}
\usepackage{newtx}
% a general purpose macro
% https://tex.stackexchange.com/a/480801/4427
\newcommand{\xmathpalette}[2]{\mathchoice
{#1\displaystyle\textfont{#2}}%
{#1\textstyle\textfont{#2}}%
{#1\scriptstyle\scriptfont{#2}}%
{#1\scriptscriptstyle\scriptscriptfont{#2}}%
}
\NewCommandCopy{\originaloverline}{\overline}
\makeatletter
\RenewDocumentCommand{\overline}{O{2}m}{\xmathpalette\overline@{{#1}{#2}}}
\newcommand{\overline@}[3]{\overline@@#1#2#3}
\newcommand{\overline@@}[4]{%
% #1 = math style, #2 = font size, #3 = clearance, #4 = subformula
\vbox{\m@th % no math surround
\vskip\fontdimen8#23
\hrule height \fontdimen8#23
\vskip#3\fontdimen8#23
\hbox{$#1#4$}
}%
}
\makeatother
\begin{document}
$\overline{k}$ $\bar{k}$
$\scriptstyle \overline{k}$ $\scriptstyle \bar{k}$ % script style
$\overline[3]{k}$ $\originaloverline{k}$ % comparison
\end{document}

\overline, or could you use\bar? Please advise.\baris fine, it actually looks better in my opinion\bar{k}is much less obtrusive than the one produced by\overlinek{k}, is your issue (mostly) resolved by swithcing from\overlineto\bar?\barthe vertical spacing is less and the line looks "more connected" to the k. I am still interested in a solution with\overline, but purely out of curiosity.newtx, I edited my answer.