adb restore  does nothing
I guess the adb from sudo apt-get install android-tools-adb was a bit too out of date. I downloaded the latest version from https://developer.android.com/studio/releases/platform-tools.html and extracted just the adb command, which is Android Debug Bridge version 1.0.39 Version 0.0.1-4500957, ran it and my phone prompted for a "full restore" which sounds scary but in the end just did a full restore of the FreeOTP. After it was done I have my keys back, yay!