Unable to SSH using public key from Ubuntu 22 VM

[johnnyringo]

I migrated from a Debian 9 to Ubuntu 22 bastion host this week, and am unable to SSH to CheckPoint R80.40 gateways using public key authentication.   Initially I was unable to SSH to the CheckPoints at all, but was able to fix that but adding the following lines to /etc/ssh/ssh_config:

KexAlgorithms +diffie-hellman-group14-sha1
HostKeyAlgorithms=+ssh-dss

This fixed the connection, and I can now authenticate via username/password.  However, public key auth is failing.  

It's a bit of a concern since we have multiple R80.40 (and a few R80.30) devices in public cloud, where public ssh key auth is the only way to do initial configuration (username/password only works for GAIA web interface)

Server Info:

ssh -V
OpenSSH_7.8p1, OpenSSL 1.1.1n 15 Mar 2022

Client Info:

lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 22.04.1 LTS
Release: 22.04
Codename: jammy

ssh -V
OpenSSH_8.9p1 Ubuntu-3, OpenSSL 3.0.2 15 Mar 2022