Android TV and Fire TV devices may require that any computer connecting by adb, "authorize", via a pop-up dialog on the device that appears when you press the "Connect" button, or manually connect via the command-line.
On your Android TV or Fire TV device screen, look for a pop-up dialog similar to the images below:
For Android TV:
For the Fire TV:
With your remote, confirm the connection and check "Always Allow..."
An authorization "key" is then stored in a .android directory on your PC/Mac in your home directory and in a protected directory on your Android TV or Fire TV device.
If the authorization dialog does not appear, try deleting/renaming the .android/adbkey and .android/adbkey.pub files in your $HOME directory. This should force your device to reauthorize.