Bootstrap 4 : Vertically Align Navigation Links when Logo Increases the Navbar Height

I think you can remove top and bottom padding from links and add height and line-height to it. Also remove padding from .navbar-brand.

Just add this CSS:

.navbar-brand {
  padding: 0;
}
.navbar-nav .nav-link {
  padding-top: 0;
  padding-bottom: 0;
  height: 50px;
  line-height: 50px;
}

CODEPEN

I ran into a similar situation where I'd like to vertically align my nav-items.

Step 1: Add the classes d-lg-flex align-items-center to your .navbar-nav parent element. This ensures that you can align child items using flex-utilities

Step 2: Add the h-100 class to each child nav-item. Nav-item has no defined height that I'm aware of. With nav-item's defined height, it will follow the flex rules set above by align-items-center.

Step 3: Please check my external links in my codepen because the navbar requires additional js.

Here is a working example of vertically centered nav-items https://codepen.io/b3bold/pen/rvMwzN

<nav class="navbar navbar-expand-md p-3 mb-2 navbar-light bg-white text-dark">   
  <a class="navbar-brand" href="#">
    <img src="https://i.stack.imgur.com/snRuy.jpg" />
  </a>

  <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation">
    <span class="navbar-toggler-icon"></span>
  </button>

  <div class="collapse navbar-collapse" id="navbarNav">
    <ul class="navbar-nav ml-auto text-center w-100 justify-content-between ml-lg-0 d-lg-flex align-items-center">
      <div class="nav-item h-100"><a class="nav-link" href="#">RandomLink</a></div>
      <div class="nav-item h-100"><a class="nav-link"href="#">Some Really Long Link as an Example of Vertical </a></div>
      <div class="nav-item h-100"><a class="nav-link" href="#">RandomLink</a></div>
      <div class="nav-item h-100"><a class="nav-link" href="#">RandomLink</a></div>
      <div class="nav-item h-100"><a class="nav-link" href="#">RandomLink</a></div>
    </ul>
  </div>
</nav>