You have two options:
Install vim-nox. From the package description (apt-cache show vim-nox),
This package contains a version of vim compiled with support for
scripting with Lua, Perl, Python 3, Ruby, and Tcl but no GUI.
Install vim-athena. From the package description (apt-cache show vim-athena),
This package contains a version of vim compiled with a ...
As noted by @Christian Brabbandt in the comment before, apparently, this is from YouCompleteMe auto-completion. As mentioned in YouCompleteMe, github about Diagnostic UI,
This turns on YCM's diagnostic display features including like the gutter signs, text highlighting, diagnostic echo and auto location list population. To disable this, I put :
You can compile Vim from source to configure which interpreter it should use. The full instructions can be found on the YouCompleteMe wiki.
It turns out the method described in the original post is correct: configuring the installation with the following options should have Vim link against Python 3.7