I experienced exactly same problem. How I resolved it is following.

1. Generated SSH-2DSA dsa.pub and dsa.ppk with puttygen on Windows

2. Converted dsa.ppk to openssh.ppk ( Conversion-> Export OPENSSH key) in puttygen

3. Loaded openssh.ppk and saved openssh.pub from Key window in puttygen

4. copied content openssh.pub to authorised_keys on server and on local windows computer

5. Voila

my $ssh2 = Net::SSH2->new(trace => -1);
#$ssh2->debug(1);
  $ssh2->connect('server_ip') or die $!;
  print $ssh2->error;
  $ssh2->auth_publickey('username','openssh.pub','openssh.ppk') or die
+ "$!\n";
my $chan = $ssh2->channel();
    $chan->blocking(0);
    $chan->exec('ls -al');
    my @output;
    while (<$chan>) { print $_; }
[download]

works with no problems